回文链表

回文链表

https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/

https://leetcode-cn.com/problems/palindrome-linked-list/solution/

栈

把所有值存到栈（数组）中，然后前后指针来检查是否为回文。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func isPalindrome(head *ListNode) bool {
    values := []int{}

    for head != nil {
        values = append(values, head.Val)
        head = head.Next
    }

    n := len(values)
    for i, v := range values[:n/2] {
        if v != values[n-1-i] {
            return false
        }
    }

    return true
}

快慢指针

使用快慢指针，慢指针走 1 步时快指针走 2 步，这样在快指针到达末尾时，慢指针恰好在链表的中间。

反转后半部分链表，然后检查是否是回文，这样时间复杂度还是 O(n)，空间复杂度只有 O(1)了。

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
34
35
36
37
38
39
40
41
func isPalindrome(head *ListNode) bool {
    if head.Next == nil {
        return true
    }

    fast, slow := head, head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    if fast != nil { // 奇数个节点
        slow = slow.Next // 跳过节点中点，只逆转后半截
    }

    revHead := reverse(slow)

    for revHead != nil {
        if head.Val != revHead.Val {
            return false
        }
        head = head.Next
        revHead = revHead.Next
    }
    return true
}

func reverse(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head

    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}

递归

类似于二叉树的后序遍历，单链表也能从后往前遍历，只要在调用递归函数之后进行访问操作就可以了，例如：（JAVA）

1
2
3
4
5
6
private void printListNode(ListNode head) {
    if (head == null)
        return;
    printListNode(head.next);
    System.out.println(head.val);
}

因此也可以在递归中从后往前走的时候，用一个全局变量来储存从前往后走的指针，递归每走一步，这个指针也往前走一步，这样就能实现两头的访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var temp *ListNode

func isPalindrome(head *ListNode) bool {
    temp = head
    return check(head)
}

func check(node *ListNode) bool {
    if node == nil {
        return true
    }
    res := check(node.Next) && node.Val == temp.Val
    temp = temp.Next
    
    return res
}

可以把递归视作函数调用栈，因此空间复杂度依然是 O(n)。