8.12回文链表 - WisperDin/blog GitHub Wiki

描述

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

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

思路

对于回文类型的题目，要特别注意奇数个元素和偶数个元素时算法的处理情况

判断是否为回文链表，则意味着需要判断链表前半部分元素与后半部分元素是否一一对应

1->2->2->1

1,2 倒序对应 2,1

1. 找到链表的中点，可以通过快慢指针（对每一次，快指针走两步，慢指针走一步），当快指针走到末尾时，慢指针到达链表的 中点或者两个中点元素偏左一个

   1,2,2,1 --> 找到处于1位置的2

   1,2,3,2,1 --> 找到3

2. 将另一半链表进行反转，从而将链表分成两条，如果是回文链表的话，这两条链表应该一样

   1,2,2,1 --> [1,2] [1,2]

   1,2,3,2,1 --> [1,2] [1,2]

package PalinodromeList

// https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/6/linked-list/45/


type ListNode struct {
	Val int
	Next *ListNode
}

func recList(head *ListNode) *ListNode{
	if head.Next==nil{
		return head
	}
	newHead := recList(head.Next)
	//reverse
	if head.Next.Next==nil{
		//arrive the last 2 pos (right order)
		head.Next.Next = head
		head.Next = nil
	}
	return newHead
}


func isPalindrome(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return true
	}
	slowPtr := head
	fastPtr := head

	for true {
		if fastPtr.Next == nil{
			break
		}
		fastPtr = fastPtr.Next
		if fastPtr.Next == nil{
			break
		}
		fastPtr = fastPtr.Next


		if slowPtr.Next == nil{
			//unpossible
			return false
		}
		slowPtr = slowPtr.Next
	}

	//find middle pos or left of the two middle
	if slowPtr.Next == nil{
		//unpossible
		return false
	}
	slowPtr = slowPtr.Next
	slowPtr = recList(slowPtr)
	newPtr := head
	for slowPtr!= nil {

		if newPtr.Val != slowPtr.Val{
			return false
		}
		slowPtr = slowPtr.Next
		newPtr = newPtr.Next
	}
	return true

}