LeetCode 筆記 - 19. Remove Nth Node From End of List

Posted on

題目在此 19. Remove Nth Node From End of List

image 26

給一個 Linked list，請移除後面數過來第 n 個 node

解題思維

這題使用了 Two Pointers

第一個關鍵是 root 移動了 n + 1 次之後，remove pointer 才跟著開始移動
而這樣的設計會讓 remove pointer 停在要移除的 node 的前一個 node
接下來就是把 remove.next 指向 remove.next.next 就可以了

第二個關鍵是，我多一個 node 來抓住 head
這樣可以解決只傳了一個 node 進來，root 跟 remove 兩個 pointer 無法操作的問題

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        
        root = ListNode(None, next=head)
        
        remove = current = root
        
        index = 0
        while current:
            current = current.next
            index += 1
            
            if index > n + 1:
                remove = remove.next
        
        if remove.next:
            remove.next = remove.next.next
            
        return root.next

也許你也會想看看