未分類

Remove Duplicates from Sorted List II

Go, LeetCode, LinkedList

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example:

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

解答思路:

之前有一遍Remove Duplicates from Sorted List，原先是先不管後頭的值是否出現重覆，先將第一個節點保留於原LinkedList之中，當後頭出現重覆的值才做嫁接跳過該節點，不過這次是只要該值重覆就要完全跳過，所以做法上有很大的不同，要遍歷到目前的節點與前一個的節點不同值才考慮是否要保留先前的節點，如果前一個是沒有重覆的節點可以保留下來的話，還要記得將前一個節點做註記，以利接下來如果後續再次出現沒有重覆的節點時，可以拿來與先前未重覆的節點做嫁接。

程式碼解說:

因為這次操作會影響到原本LinkedList中第一個節點的存留，所以就需要再最前頭新增一個頭節點來確保第一個節點能與其它節點一樣能有操作上的一致性，而頭節點的預設值為int的32位元極大值，原本的LinkedList則是接在頭節點的後頭，並先將前一個節點與前一個不重覆的節點都指向頭節點接著才開始遍歷原本的LinkedList，一邊遍歷的同時一樣一邊記錄前一個節點的位置，而如思路所寫，這邊的做法是遍歷到與前一個的節點不同值才考慮是否要保留先前的節點，所以當目前節點的值與前一個節點的值不同，除了將暫存值改為目前節點的值與重置重覆的註記之外，在其之前判斷前一個節點是否曾出現重覆值的情況，如果沒有才與之前也沒有重覆、獨特的節點做嫁接，再將前一個節點註記為新的嫁接點，而如果目前節點的值與前一個節點的值相同則將重覆的註記設為true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
isDuplicate := true
tmp := math.MaxInt32
header := &ListNode{tmp, head}
preNode := header
primeNode := header
for head != nil {
	if tmp != head.Val {
		if !isDuplicate {
			primeNode.Next = preNode
			primeNode = preNode
		}
		tmp = head.Val
		isDuplicate = false
	} else {
		isDuplicate = true
	}
	preNode = head
	head = head.Next
}

因為判斷是要到下一個節點之後才決定前一個節點是否要保留，所以可能最後一個節點就沒有被判斷到，因此還要再次判斷剩下的節點是否重覆，如果是則一樣做嫁接，否則就將要嫁接到的位置指向nil，最後便回傳之前所新增頭節點所連結的下一個位置(也就是新的LinkedList起頭的位置)

1
2
3
4
5
6
if !isDuplicate {
	primeNode.Next = preNode
} else {
	primeNode.Next = nil
}
return header.Next

完整程式碼:

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
func deleteDuplicates(head *ListNode) *ListNode {
	isDuplicate := true
	tmp := math.MaxInt32
	header := &ListNode{tmp, head}
	preNode := header
	primeNode := header
	for head != nil {
		if tmp != head.Val {
			if !isDuplicate {
				primeNode.Next = preNode
				primeNode = preNode
			}
			tmp = head.Val
			isDuplicate = false
		} else {
			isDuplicate = true
		}
		preNode = head
		head = head.Next
	}
	if !isDuplicate {
		primeNode.Next = preNode
	} else {
		primeNode.Next = nil
	}
	return header.Next
}

總結:

給予LinkedList，如果當中出現有重覆值的節點就要將其完全跳過，其做法是要遍歷到目前的節點與前一個的節點不同值才考慮是否要保留先前的節點，如果前一個是沒有重覆的節點可以保留下來的話，還要記得將前一個節點做註記，以利接下來如果後續再次出現沒有重覆的節點時，可以拿來與先前未重覆的節點做嫁接。

分享到