leetcode234 回文链表

题目

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

示例

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

解析

先快慢指针找到中间节点，然后反转后半个链表，再同时比较两个链表

func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	slow := head
	fast := head
	prev := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	new := reverseList(slow)
	for prev != nil && new != nil {
		if prev.Val != new.Val {
			return false
		}
		prev = prev.Next
		new = new.Next
	}
	return true
}
func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}
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