Solution)
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# Dummy node that allows us to access head
dummy = ListNode(0, head)
# Dictionary that saves {index:node}
indexDic = {0:dummy}
# Save {index:node} to indexDic
nodeIndex = 1
while head:
indexDic[nodeIndex] = head
head = head.next
nodeIndex += 1
# Find the index whose node has to be removed
wantedIndex = nodeIndex - n
# Link the nodes surrounding the wanted node
indexDic[wantedIndex-1].next = indexDic[wantedIndex].next
return dummy.next
Problem: LeetCode
Time Complexity: O(n)
Space Complexity: O(n)
* n = number of nodes
Explanation)
To solve this problem in one pass, I used an extra memory of dictionary.
This dictionary will save the nodes according to their indexes using one-based indexing.
Using those indexes, we can easily access nodes surrounding the node that needs to be deleted.
Instead of actually deleting the node, we'll connect the surrounding nodes.
Initialization)
Variable dummy is a dummy node that will have head as its next node. We do this to access start of the linked list whenever we want.
Dictionary indexDic will save the nodes according to their one-based indexes. So dummy's index will be a zero.
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
indexDic = {0:dummy}
Saving nodes to indexDic)
While iterating the linked list, we'll save the nodes with their indexes to indexDic.
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
indexDic = {0:dummy}
nodeIndex = 1
while head:
indexDic[nodeIndex] = head
head = head.next
nodeIndex += 1
Find the index whose node needs to be deleted)
To find the index whose node needs to be deleted, we have to subtract n from nodeIndex.
Once we find wantedIndex, we need to find the surrounding nodes.
Those nodes will be indexDIc[wantedIndex-1] and indexDic[wantedIndex].next
Now we just need to connect them, meaning we deleted the wanted node out of the linked list.
After connecting them, let's return the start of the linked list by returning dummy.next
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# Initialization
nodeIndex = 1
while head:
indexDic[nodeIndex] = head
head = head.next
nodeIndex += 1
wantedIndex = nodeIndex - n
indexDic[wantedIndex-1].next = indexDic[wantedIndex].next
return dummy.next
I had to use extra memory to access the wanted node, but you can also solve this with constant memory. You can use two pointers slow and fast, which seems to be used a lot in linked-list problems. Check this solution!
'[LeetCode] > [Medium]' 카테고리의 다른 글
[Top Interview 150] 61. Rotate List (0) | 2023.08.30 |
---|---|
[Top Interview 150] 82. Remove Duplicates from Sorted List II (0) | 2023.08.29 |
[Top Interview 150] 92. Reverse Linked List II (0) | 2023.08.25 |
[Top Interview 150] 138. Copy List with Random Pointer (0) | 2023.08.24 |
[Top Interview 150] 150. Evaluate Reverse Polish Notation (0) | 2023.08.23 |