LeetCode，Go 判斷一個鏈表是否爲迴文鏈表
力扣題目：
請判斷一個鏈表是否爲迴文鏈表。
-
來源：力扣（LeetCode）
-
鏈接：https://leetcode-cn.com/problems/palindrome-linked-list/
解題
- 將值複製到數組中後用雙指針法
-
我們首先遍歷鏈表，將鏈表中的值（Val）保存到一個數組中
-
然後對數組進行遍歷，我們可以使用雙指針法來比較兩端的元素，並向中間移動。一個指針從起點向中間移動，另一個指針從終點向中間移動。
-
每移動一步就比較一次值，如果值不相等，說明不是迴文鏈表。
如下 Go 實現的解法：
func isPalindrome(head *ListNode) bool {
s := []int{}
for ; head != nil; head = head.Next {
s = append(s, head.Val)
}
l := len(s)
for k, v := range s[:l/2] {
if v != s[l-1-k] {
return false
}
}
return true
}空間複雜度：O(n)，這種解法，我們使用了一個數組列表存放鏈表的元素值。n 指的是鏈表的元素個數。
進階：你能否用 O(n) 時間複雜度和 O(1) 空間複雜度解決此題？
- 快慢指針
我們可以將鏈表的後半部分進行反轉（修改鏈表結構），然後將前半部分和後半部分進行比較。比較完成後我們再將鏈表恢復原樣。雖然不需要恢復也能通過測試用例。
整個流程可以分爲以下五個步驟：
-
找到前半部分鏈表的尾節點。
-
反轉後半部分鏈表。
-
判斷是否迴文。
-
恢復鏈表。
-
返回結果。
步驟 1 我們使用**「快慢指針」**在一次遍歷中找到：慢指針一次走一步，快指針一次走兩步，快慢指針同時出發。當快指針移動到鏈表的末尾時，慢指針恰好到鏈表的中間。通過慢指針將鏈表分爲兩部分。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
//找到前半部分鏈表的尾節點
endNode := end(head)
//翻轉後半部分鏈表
fanNode := fan(endNode.Next)
//判斷是否迴文
n1 := head
n2 := fanNode
for n2 != nil {
if n1.Val != n2.Val {
return false
break
}
n1 = n1.Next
n2 = n2.Next
}
endNode.Next = fan(fanNode)
return true
}
func end (head *ListNode) *ListNode{
fast := head
slow := head
for fast.Next != nil && fast.Next.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func fan(head *ListNode) *ListNode{
var pre, cur *ListNode = nil, head
for cur != nil {
tmpNode := cur.Next
cur.Next = pre
pre = cur
cur = tmpNode
}
return pre
}「複雜度分析」
-
時間複雜度：O(n)，其中 n 是鏈表的大小。
-
空間複雜度：O(1)。我們只會修改原本鏈表中節點的指向，而在堆棧上的堆棧幀不超過 O(1)。
有什麼問題，可以公衆號內回覆或加我微信交流。
微信公衆號
gophpython
我的微信
wucs_dd
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Z1cDEEDL1DQXwkSHKmdcfw