Palindrome Linked List

题目描述

回文链表：

判断一个链表是否为回文链表

示例：

输入：1 -> 2
输出：false

解法

解法一：将元素放入数组，再用双指针

• 时间复杂度：O(n)

• 空间复杂度：O(n)

代码比较简单，省略。

解法二：递归

• 时间复杂度：O(n)

• 空间复杂度：O(n)

代码不想写。

解法三：双指针

• 时间复杂度：O(n)

• 空间复杂度：O(1)

func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }

    // 寻找中位节点
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    // 反转后半部分
    head2 := reverse(slow)
    tail := head2
    // 判断是否回文
    for head != nil && tail != nil {
        if head.Val != tail.Val {
            return false
        }
        tail = tail.Next
        head = head.Next
    }
    // 恢复反转链表
    reverse(head2)
    return true
}

// 翻转链表
func reverse(head *ListNode) *ListNode {
    var dummy *ListNode
    for head != nil {
        next := head.Next
        head.Next = dummy
        dummy = head
        head = next
    }
    return dummy
}