Palindrome Linked List

题目介绍

LeetCode 234. Palindrome Linked List。

复杂度

时间复杂度: O(n), 空间复杂度: O(1)

解题思路

这一题思路比较多，比如赋值到数组里面在去进行判断，要满足 O(1) 的空间复杂度，需要考虑下。

大概分为三个函数：

• 使用快慢指针找到链表的中间节点（第一次看到这个用途，很巧妙）；
• 使用反转链表函数反转后半部分链表；
• 进行比较并将后半部分链表反转回去，保证原链表的完整性。

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        let middle = endOfFirstHalf(head)
        var first = head
        var second = reverseList(middle?.next)
        while(second != nil) {
            if first?.val != second?.val {
                reverseList(middle?.next)
                return false
            }
            first = first?.next
            second = second?.next
        }
        reverseList(middle?.next)
        return true
    }

    @discardableResult
    func reverseList(_ head: ListNode?) -> ListNode? {
        var pre: ListNode? = nil
        var cur = head
        while(cur != nil) {
            let t = cur?.next
            cur?.next = pre
            pre = cur
            cur = t
        }
        return pre
    }

    func endOfFirstHalf(_ head: ListNode?) -> ListNode? {
        var fast = head
        var slow = head
        while(slow?.next != nil && fast?.next?.next != nil) {
            fast = fast?.next?.next
            slow = slow?.next
        }
        return slow
    }
}

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2020/03/13/PalindromeLinkedList/