234. 回文链表

easy

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

快慢指针 + 反转

利用快慢指针将链表分割成前后两部分，然后反转后半部分链表，就可以一一比较了

 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
package linked_list

func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	slow, fast := head, head
	for fast.Next != nil && fast.Next.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
    // slow 即为前半部分的尾节点，如果链表为奇数，那么slow为中间节点

	startOfSecondHalf := reverseList(slow.Next) // 后半部分的头节点 顺便反转一下后半部分

	p, q := head, startOfSecondHalf
	for q != nil {
		if p.Val != q.Val {
			return false
		}
		p, q = p.Next, q.Next
	}
	return true

}

func reverseList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var pre, cur *ListNode = nil, head
	for cur != nil {
		tmp := cur.Next
		cur.Next = pre
		pre, cur = cur, tmp
	}
	return pre
}

时间复杂度：O(n)，其中 n 指的是链表的大小。

空间复杂度：O(1)，我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)