LeetCode-234.回文链表 - sheep44044的小站

链表#

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

1
输入：head = [1,2,2,1]
2
输出：true

示例 2：

1
输入：head = [1,2]
2
输出：false

自己的解法(哈希+左右指针)

手撕，单纯做出来还是很简单的，不过13ms确实有点慢

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func isPalindrome(head *ListNode) bool {
9
    if head == nil {
10
        return true
11
    }
12

13
    cur := head
14
    res := []int{}
15
    for cur != nil {
16
        res = append(res, cur.Val)
17
        cur = cur.Next
18
    }
19

20
    left, right := 0, len(res)-1
21
    for left < right {
22
        if res[left] != res[right] {
23
            return false
24
        }
25
        left++
26
        right--
27
    }
28

29
    return true
30
}

很有趣的解法(快慢指针+反转链表+左右指针)

1
func isPalindrome(head *ListNode) bool {
2
    if head == nil || head.Next == nil {
3
        return true
4
    }
5

6
    slow, fast := head, head
7
    for fast != nil && fast.Next != nil {
8
        slow = slow.Next
9
        fast = fast.Next.Next
10
    }
11

12
    var pre *ListNode
13
    cur := slow
14
    for cur != nil {
15
        next := cur.Next
16
        cur.Next = pre
17
        pre = cur
18
        cur = next
19
    }
20

21
    left := head
22
    right := pre
23
    for right != nil {
24
        if right.Val != left.Val {
25
            return false
26
        }
27

28
        left = left.Next
29
        right = right.Next
30
    }
31

32
    return true
33
}