LC234.回文链表

1. 题目

• 234. 回文链表

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[1, 10^5] 内
• 0 <= Node.val <= 9

进阶： 你能否用O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

2. 思路

• 首先，我们找到链表的中间节点
• 然后，通过中间节点的下一个节点，作为后半段链表的头节点
• 接着，反转后半段链表，再去比对后半段链表和前半段链表，是否逐个相等，即可得到答案。

3. 代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }

    first := firstPart(head)
    second := reverseList(first.Next)

    p1 := head
    p2 := second

    for  p2 != nil {
        if p1.Val != p2.Val {
            return false 
        }

        p1 = p1.Next
        p2 = p2.Next
    }

    return true
}

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    var cur = head

    for cur != nil {
        next := cur.Next 

        cur.Next = prev
        prev = cur
        cur = next
    }

    return prev
}

// 1 --> 2 --> 3 : find 2
// 1 --> 2 --> 3 --> 4: find 2
func firstPart(head *ListNode) *ListNode {
    fast := head
    slow := head 

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

    return slow 
}