未分類

Palindrome Linked List

Go, LeetCode, LinkedList, TwoPointers

Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:

Could you do it in O(n) time and O(1) space?

提示 解題應用
LinkedList Pointer

Default:

1
2
3
4
5
6
7
8
9
10
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
}

解答思路:

在寫之前會發現到Follow up希望你能達到的條件，不過我認為要嚴格達到是非常具有爭議性的，因為要做回文的判斷，偏偏此題LinkedList的節點又是不可逆，此外用字串來強制儲存正反兩面做比較(可以參考:Valid Palindrome)，畢竟存的值不是字串會有正負數上處理的麻煩及負號會導致不對稱，所以最後的結論就是先找到中間節間為開始倒著回去的部分，接著就是將原本中間到最後的部分反轉，便同時與前面的部分開始遍歷比較是否相同，而爭議點在於反轉所花費的空間與時間，總之就先以此方式來當作目前最佳的解決方案。

程式碼解說:

一開始先判斷LinkedList是否為nil，接著就是要來找出中間節點的位置，同時兩個指標以1:2的速度來遍歷整個LinkedList，當速度比較快的指標到底時，此時比較慢的指標會位在前半部最後一個節點的位置上，正如先前所說，這時就可以將後半部的部分給反轉，而在那之前要先將比較慢的指標位置往後移一格，變成後半LinkedList的開頭，最後與前半部開始同時遍歷一一檢查值是否相同，直到後半部的節點到達底部都沒有問題才回傳true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	fast := head.Next
	slow := head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	slow = reverse(slow.Next)
	for slow != nil {
		if head.Val != slow.Val {
			return false
		}
		head = head.Next
		slow = slow.Next
	}
	return true
}

先前就有題目需要反轉LinkedList，此時就可以派上用場，詳細的解說可以參考:Reverse Linked List

1
2
3
4
5
6
7
8
9
10
11
func reverse(head *ListNode) *ListNode {
	var preNode *ListNode
	var tmp *ListNode
	for head != nil {
		tmp = head
		head = head.Next
		tmp.Next = preNode
		preNode = tmp
	}
	return tmp
}

完整程式碼:

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
func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	fast := head.Next
	slow := head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}
	slow = reverse(slow.Next)
	for slow != nil {
		if head.Val != slow.Val {
			return false
		}
		head = head.Next
		slow = slow.Next
	}
	return true
}
func reverse(head *ListNode) *ListNode {
	var preNode *ListNode
	var tmp *ListNode
	for head != nil {
		tmp = head
		head = head.Next
		tmp.Next = preNode
		preNode = tmp
	}
	return tmp
}

總結:

若要檢查一單向LinkedList是否為回文，且其節點所儲存的值非為字串，此時可以先找出中間節點的位置，接著將後半的LinkedList做反轉，最後再同時與前面的部分開始遍歷比較是否相同。

分享到