跳转至

LC234 - 回文链表

PalindromeLinkedList.go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package LinkedList

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    // (1) 快慢指针寻找链表中点
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    if fast.Next != nil {
        fast = fast.Next
    }
    // (2) 反转后面的链表
    reverseList(slow)
    // (3) 遍历两个链表逐个节点比较
    ptr1, ptr2 := head, fast
    for ptr1 != nil && ptr2 != nil && ptr1.Val == ptr2.Val {
        ptr1 = ptr1.Next
        ptr2 = ptr2.Next
    }
    var result bool
    if ptr1 == nil || ptr2 == nil {
        result = true
    } else {
        result = false
    }
    // (4) 反转回后面的链表
    reverseList(fast)
    return result
}

reverseList函数在LC206中实现。

此处之所以选择反转后面的链表而非前面的链表，是为了防止出现链表断开，从而简化编码难度。