golang力扣leetcode 234.回文链表_golang 回文链表

234.回文链表

234.回文链表

题解

思路：取中点分成两个链表，翻转第二个，开始比较，注意其中一个为nil就可以停止了，因为有可能节点为奇数的情况

代码

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func findMiddle(head *ListNode) *ListNode {
	slow := head
	fast := head.Next
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow
}
func reverseList(head *ListNode) *ListNode {
	curr := head
	var p *ListNode
	for curr != nil {
		next := curr.Next
		curr.Next = p
		p = curr
		curr = next
	}
	return p
}
func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	mid := findMiddle(head)
	tail := reverseList(mid.Next)
	for head != nil && tail != nil {
		if head.Val != tail.Val {
			return false
		}
		head = head.Next
		tail = tail.Next
	}
	return true
}
func main() {

}
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
39
40
41
42
43
44
45