Note this one
head of a linked list, remove the
nth node from the end of the list and return its head.
- The number of nodes in the list is
- \(1 \leq sz \leq 30\).
- \(0 \leq Node.val \leq 100\).
- \(1 \leq n \leq sz\).
Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Input: head = , n = 1 Output:  Input: head = [1,2], n = 1 Output: 
2.1. Understanding the problem
From the provided code we can see it's a singly linked list.
We can use
fast_pos that will reach the end of the list, and
slow_pos that will be
n node(s) away from
fast_node. Slow node will be tracking the previous node of the node to be removed.
Given that the trivial case
, we have
slow_node = head,
slow_pos = 0 and
fast_node = head and
fast_pos = 0.
In the end we want to first have
slow_node to be
n nodes away and then move both of them to the next node, until
fast_node reaches the end of the list.
slow_node will be the node that is connected to
fast_node, and the node between them will be removed.
Incorrect algorithm where I put progression of space between
fast_node by moving
fast_node moving together, under the same while loop.
In this case I had difficulty handling the edge case with
head being the element to be removed via checking if
fast_node is None.
I had no way of returning from the
while loop finishes, I have no way of distinguishing the following situations so I won't know if I need to remove the head:
n = 3
n = 3
1. Initialise ~fast_node = head~, ~fast_pos = 0~, ~slow_node = head~, ~slow_pos = 0~ 2. while ~fast_node.next~ 1. if ~fast_pos - slow_pos < n~ 1. ~fast_node = fast_node.next~, ~fast_pos += 1~ 2. if ~fast_pos - slow_pos == n~ 1. ~fast_node = fast_node.next~, ~fast_pos += 1~ 1. ~slow_node = slow_node.next~, ~slow_pos += 1~
def removeNthFromEnd(self, head, n): """ :type head: ListNode :type n: int :rtype: ListNode """ fast_node = head fast_pos = 0 slow_node = head slow_pos = 0 while fast_pos - slow_pos < n: fast_node = fast_node.next fast_pos += 1 # critical part if fast_node is None: return head.next while fast_node.next: fast_node = fast_node.next slow_node = slow_node.next slow_node.next = slow_node.next.next return head
184.108.40.206. Time complexity:
220.127.116.11. Space complexity:
2.4. Leetcode solution
<<imports for typing>>
2.4.1. Time complexity:
2.4.2. Space complexity:
3. More analysis
3.1. General thoughts
I had to check Leetcode solution for this one as my original wasn't right.
I think the hardest part is again the edge cases, especially how to handle a linked list of only one element, although it's not really relevant in this case, and how to remove the head node.