【日拱一卒】連結清單——回文判斷

如何判斷一個連結清單是否是回文連結清單

需求

判斷一個連結清單是否是回文連結清單

回文的形式大家應該都知道，類似

abcba
或者
abccba      

這種對稱的方式都是回文。

難點

如果将連結清單形式換成數組，是不是就簡單很多了。針對一個長度為n的數組，我們可以一一比對節點0和節點n-1，節點1和節點n-2，直到收尾索引相等。

但是這裡說的是連結清單，顯然周遊完整個連結清單，找到尾結點，然後再回溯進行比較顯得有些不切實際，況且這裡并不是雙向連結清單。

是以這裡就要換個思路，重點是從回文的對稱性着手。

思路

關鍵字：快慢指針、連結清單反轉

1、初始化兩個指針快指針和慢指針，慢指針每次走一步，快指針每次走兩步

2、依次周遊整個連結清單，直到快指針周遊完連結清單

此時fast指針已經率先到達連結清單的尾結點，停止周遊。因為該連結清單包含奇數個元素，是以slow節點需要再移動一步。指向節點2。

3、此時借助慢指針将後半部分連結清單反轉

反轉後連結清單頭指針為pre

4、依次周遊比較原來連結清單和反轉後的連結清單pre的值是否相等，直到pre周遊到尾結點。

有了如上思路，寫出對應代碼就是順理成章的事了。

代碼實作

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

	// 快慢指針，快指針每次移動兩步，慢指針每次移動一步
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	//如果是奇數，則慢指針再移動一步，到達中心點
	if fast != nil {
		slow = slow.Next
	}

	// 慢指針反轉
	var pre *ListNode = nil
	for slow != nil {
		pre, slow, slow.Next =slow, slow.Next, pre
	}

	cur := head
	for cur != nil && pre != nil {
		if cur.Val == pre.Val {
			cur = cur.Next
			pre = pre.Next
		} else {
			return false
		}
	}

	return true
}
      

　　

不忘初心

老王：你不好好種地，你以後長大能幹什麼

小王：學算法

老王：學算法？！你數組、連結清單、棧、隊列、堆、排序、查找都整不明白，你學什麼算法

小王：我隻學連結清單回文判斷

老王：。。。

如果您覺得閱讀本文對您有幫助，請點一下“推薦”按鈕，您的“推薦”将是我最大的寫作動力！如果您想持續關注我的文章，請掃描二維碼，關注JackieZheng的微信公衆号，我會将我的文章推送給您，并和您一起分享我日常閱讀過的優質文章。