未分類

Remove Linked List Elements

Go, LeetCode, LinkedList

Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example:

1
2
Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6
Return: 1 --> 2 --> 3 --> 4 --> 5
提示 解題應用
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 removeElements(head *ListNode, val int) *ListNode {
}

解答思路:

總覺得類似的題目非常的多，而一樣為了要確保操作上的一致性，所以在第一個節點前再加上一個頭節點，接著就是找到目標節點然後對其做嫁接，至於要不要再多寫一行去釋放其記憶體就看個人，只是要記得再往下一個節點尋找時要記錄前一個節點的位置，畢竟節點設計的遍歷是不可逆，記錄後便能直接進行嫁接而不需再去尋找前一個節點的位置。

程式碼解說:

正如前述為了要確保一致性，所以就先初始化一個節點然後指向原本第一個節點的位置，而且最後仍須回傳整個LinkedList的第一個節點，只管回傳頭節點的所指向的下一個位置，不需要擔心如果是前面節點被砍掉還要判斷回傳後頭節點的問題，不過這次我們就直接從第一個節點開始，而不是從我們新增的頭節點開始，因為檢查自己加頭節點的值根本沒有意義，同時也要記得要記錄前一個節點的位置，方便在迴圈進行節點遍歷而找到目標節點時進行的嫁接，在嫁接時可能會出現連續要跳過好幾個目標節點，這時前一個節點的位置就不需要改變，一直到沒有再嫁接的狀況出現，當前節點開始繼續往下移動，紀錄前一個節點的位置才需要隨著改變

1
2
3
4
5
6
7
8
9
10
11
12
13
header := &ListNode{}
var preNode *ListNode
header.Next = head
preNode = header
for head != nil {
	if head.Val == val {
		preNode.Next = head.Next
	} else {
		preNode = head
	}
	head = head.Next
}
return header.Next

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func removeElements(head *ListNode, val int) *ListNode {
	header := &ListNode{}
	var preNode *ListNode
	header.Next = head
	preNode = header
	for head != nil {
		if head.Val == val {
			preNode.Next = head.Next
		} else {
			preNode = head
		}
		head = head.Next
	}
	return header.Next
}

總結:

在一個LinkedList中如果要移除任一個目標節點，在操作之前可以再第一個節點前再加上一個頭節點，以確保後續迴圈在操作上第一個節點也能與其它節點達成一致性。

分享到