判断一个链表是否回文结构

发表于

描述

给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。

题解

快慢指针

  1. 快慢指针将链表一分为二
  2. 后半部分链表反转
  3. 比较两个链表是否一致
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
package main

type ListNode struct{
    Val int
    Next *ListNode
}

func isPail(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}

	//1，找链表中点，双数就是后面的数
	fast, slow := head, head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
 
	//2，翻转链表
	var pre *ListNode
	cur := slow
	for cur != nil {
		temp := cur.Next
		cur.Next = pre
		pre = cur
		cur = temp
	}

	//3，比较链表值大小
	mid := pre
	for mid != nil {
		if mid.Val != head.Val {
			return false
		}
		mid = mid.Next
		head = head.Next
	}
	return true
}