未分類

Remove Nth Node From End of List

Go, LeetCode, LinkedList, Pointer

Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
提示 解題應用
LinkedList Pointer

Note:

Given n will always be valid.
Try to do this in one pass.

Default:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
}

解答思路:

非常典型的LinkedList題目，如果以前有碰過指標的話，那麼一定會接觸到這類題型，而這邊要你移除倒數第n個的節點，以 A B C D E 為例，如果給的 n=2 那我們要移除D的點，可惜此LinkedList僅是由頭往下做銜接，所以沒有辦法從尾走回頭，倒不如去想由頭來算是第幾個，以上述來說 5(總數)-2(從尾算)+1=4(從頭算) 不過我們一開始並不知道總數是多數，所以這邊我先遍歷一次整個List之後才真正去移除我們想要的節點。

程式碼解說:

有寫過LinkedList的應該都知道，一開始我們先在原本的List開頭插入一個自己建立的頭節點，主要是為了確保開頭節點能與後續節點操作能一致，插好新的頭節點之後塞回原本的head變數中

1
2
3
4
5
preHead := &ListNode{}
preHead.Next = head
head = preHead

接下來就能先遍歷一次取得總數之後，就可以順便拿到從頭開始算是第幾個，這邊要記得讓head指回開頭，因為這一次的遍歷讓head走到最後頭了(all需要減1因為開頭多了一個我們自訂的節點)

1
2
3
4
5
6
7
8
9
10
11
12
13
var count int
all := -1
for head != nil {
    all++
    head = head.Next
}
count = all - n + 1
head = preHead

終於能移除掉目標節點，不過我只有嫁接目標節點的頭與尾，實際上並沒有真正移除掉該節點，你也可以加一行去釋放該點的記憶體，因為要嫁接前一個與後一個節點，現有的List沒辦法讓你往回跑，所以只好新增一個變數來暫存前一個節點，將 上一個節點的Next 嫁接到 目標節點的Next 跳出迴圈就可以收工了，最後回傳原本整串List的開頭，也就是一開始我們在開頭偷塞節點的下一個。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var tmp *ListNode
for head != nil {
    count--
    tmp = head
    head = head.Next
    if count == 0 {
        tmp.Next = head.Next
        break
    }
}
return preHead.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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    var count int
    var tmp *ListNode
    preHead := &ListNode{}
    preHead.Next = head
    head = preHead
    all := -1
    for head != nil {
        all++
        head = head.Next
    }
    count = all - n + 1
    head = preHead
    for head != nil {
        count--
        tmp = head
        head = head.Next
        if count == 0 {
            tmp.Next = head.Next
            break
        }
    }
    return preHead.Next
}

總結:

對於一個從頭單向的LinkedList來說，如果要移除從尾來算的節點，倒不如先遍歷取總數後來算出從頭算為第幾個: (總數)-(從尾算)+1=(從頭算)

對於LinkedList來說，可以在頭或尾插入一個自訂的節點來確保頭或尾節點的操作能和其它節點一致。

分享到