未分類

Remove Duplicates from Sorted List

Go, LeetCode, LinkedList

Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example:

1
2
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
提示 解題應用
Linked List 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 deleteDuplicates(head *ListNode) *ListNode {
}

解答思路:

也是相當單純的Linked List應用，基本上只要注意有相同值時，該節點只需改變下一個指向的點就好，本身的位置先不需改變，因為有可能下下個的節點值還是一樣的，例如: ‘1’->1->1->2，第一個1的位置仍不動，只需把指向改到第三個1再繼續做判斷 ‘1’->1->2 其它的就沒什麼大問題了。

程式碼解說:

這邊一開始先用了flag暫存第一個節點的位置，節點往下走處理完後，最後用於回傳最初的節點，而暫存值是用來儲存前一個節點的值來判斷是否相同，這邊預設就先塞了int32位元的最大值來以防重覆，因為一定不會對第一個節點做操作，就算值重覆也是砍掉後頭的節點，所以這次也不需要有新的頭節點來確保操作一致性，之後就是利用一迴圈來不斷的遍歷整個Linked List，如果值不相同就把當前節點(連同暫存前一節點的位置)往下移動，直到回傳nil才跳開回圈，但如果相同就需要做嫁接了，這時就需要前一個節點的位置，並在前一節點的下一個直接指向當前節點的下一個，大致上來說只有前一節點的位置會因為值相同與否才做更動，另外沒有釋放節點的記憶體，所以如果你想做這個動作就不妨再多加個一行去處理

1
2
3
4
5
6
7
8
9
10
11
12
13
var flag *ListNode
var preNode *ListNode
tmp := math.MaxInt32
flag = head
for head != nil {
	if tmp != head.Val {
		tmp = head.Val
		preNode = head
	} else {
		preNode.Next = head.Next
	}
	head = head.Next
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func deleteDuplicates(head *ListNode) *ListNode {
	var flag *ListNode
	var preNode *ListNode
	tmp := math.MaxInt32
	flag = head
	for head != nil {
		if tmp != head.Val {
			tmp = head.Val
			preNode = head
		} else {
			preNode.Next = head.Next
		}
		head = head.Next
	}
	return flag
}

總結:

將Linked List中相同值的節點移除，基本上就是只有前一節點的位置會因為值相同與否才做嫁接，而當前的節點就是一直往下走到底。

分享到