19. Remove Nth Node From End of List

MediumLinked ListTwo Pointers
Leetcode Link

Problem Description

The problem presents us with a linked list and requires us to remove the nth node from the end of the list. A linked list is a linear collection of elements called nodes, where each node contains data and a reference (or link) to the next node in the sequence. The head of a linked list refers to the first node in this sequence. Our goal is to remove the nth node from the last node and return the updated list's head.

In simple terms, if we were to count nodes starting from the last node back to the first, we need to find and remove the node that sits at position 'n'. For example, if the linked list is 1->2->3->4->5 and n is 2, the resulting linked list after the operation should be 1->2->3->5, since the 4 is the 2nd node from the end.

The challenge with this task is that we can't navigate backwards in a singly linked list, so we need to figure out a way to reach the nth node from the end only by moving forward.

Intuition

To address the problem, we apply a two-pointer approach, which is a common technique in linked list problems. The intuition here lies in maintaining two pointers that we'll call fast and slow. Initially, both of these pointers will start at a dummy node that we create at the beginning of the list, which is an auxiliary node to simplify edge cases, such as when the list contains only one node, or when we need to remove the first node of the list.

The fast pointer advances n nodes into the list first. Then, both slow and fast pointers move at the same pace until fast reaches the end of the list. At this point, slow will be right before the node we want to remove. By updating the next reference of the slow pointer to skip the target node, we effectively remove the nth node from the end of the list.

The use of a dummy node is a clever trick to avoid having to separately handle the special case where the node to remove is the first node of the list. By ensuring that our slow pointer starts before the head of the actual list, we can use the same logic for removing the nth node, regardless of its position in the list.

After we've completed the removal, we return dummy.next, which is the updated list's head, after the dummy node.

Learn more about Linked List and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Solution Approach

The solution implements an efficient approach to solving the problem by using two pointers and a dummy node. Here's a step-by-step walkthrough of the implementation:

  1. Create a Dummy Node: A dummy node is created and its next pointer is set to the head of the list. This dummy node serves as an anchor and helps to simplify the removal process, especially if the head needs to be removed.

    1dummy = ListNode(next=head)

  2. Initialize Two Pointers: Two pointers fast and slow are introduced and both are set to the dummy node. This allows for them to start from the very beginning of the augmented list (which includes the dummy node).

    1fast = slow = dummy

  3. Advance Fast Pointer: The fast pointer advances n steps into the list.

    1for _ in range(n):
2    fast = fast.next

  4. Move Both Pointers: Both pointers then move together one step at a time until the fast pointer reaches the end of the list. By this time, slow is at the position right before the nth node from the end.

    1while fast.next:
2    slow, fast = slow.next, fast.next

  5. Remove the Target Node: Once slow is in position, its next pointer is changed to skip the target node which effectively removes it from the list.

    1slow.next = slow.next.next

  6. Return Updated List: Finally, the next node after the dummy is returned as the new head of the updated list.

    1return dummy.next

The algorithm fundamentally relies on the two-pointer technique to find the nth node from the end. The use of a dummy node facilitates the removal of nodes, including the edge case of the head node, with a consistent method. The space complexity is O(1) since no additional space is required aside from the pointers, and the time complexity is O(L), where L is the length of the list, as we traverse the list with two pointers in a single pass.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example Walkthrough

Let's use the linked list 1->2->3->4->5 as an example to illustrate the solution approach described above, where n is 2, meaning we want to remove the 2nd node from the end, which is the node with the value 4. Here's how the algorithm would be applied:

  1. Create a Dummy Node: We create a dummy node with None as its value and link it to the head of our list. Our list now looks like dummy->1->2->3->4->5.

  2. Initialize Two Pointers: We set both fast and slow pointers to the dummy node. They both point to dummy initially.

  3. Advance Fast Pointer: As n is 2, we advance the fast pointer n steps into the list. fast becomes:

    • After 1st step: fast points to 1
    • After 2nd step: fast points to 2

  4. Move Both Pointers: Now we move both slow and fast pointers together one step at a time until fast reaches the last node:

    • slow points to dummy and fast points to 2 (Start)
    • slow points to 1 and fast points to 3
    • slow points to 2 and fast points to 4
    • slow points to 3 and fast points to 5 (End)

    At the end of this step, slow points to the 3 and fast points to the last node 5.

  5. Remove the Target Node: Now, slow.next is pointing to the node 4, which we want to remove. We update slow.next to point to slow.next.next (which is 5), effectively removing the 4 from the list.

  6. Return Updated List: Finally, we return the next node after the dummy, which is the head of our updated list (1->2->3->5). The updated list after removal is as follows: 1->2->3->5.

The problem is solved in one pass and the node is successfully removed according to the given constraints.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next_node=None):
4        self.val = val
5        self.next = next_node
6
7class Solution:
8    def remove_nth_from_end(self, head: ListNode, n: int) -> ListNode:
9        # Create a dummy node that points to the head of the list. This helps simplify edge cases.
10        dummy_node = ListNode(next_node=head)
11      
12        # Initialize two pointers to the dummy node.
13        fast_pointer = slow_pointer = dummy_node
14      
15        # Move fast pointer n steps ahead so it maintains a gap of n between slow pointer.
16        for _ in range(n):
17            fast_pointer = fast_pointer.next
18      
19        # Move both pointers until fast pointer reaches the end of the list,
20        # keeping the gap of n. Thus, the slow pointer will point to the node
21        # just before the one to be removed.
22        while fast_pointer.next:
23            slow_pointer, fast_pointer = slow_pointer.next, fast_pointer.next
24      
25        # Remove the nth node from the end by skipping over it with the slow pointer.
26        slow_pointer.next = slow_pointer.next.next
27      
28        # Return the new head, which is the next node of dummy node.
29        return dummy_node.next
30
1// Definition for singly-linked list node.
2class ListNode {
3    int val;
4    ListNode next;
5  
6    // Constructor to initialize the node without a next node
7    ListNode() {}
8  
9    // Constructor to initialize the node with a value
10    ListNode(int val) { this.val = val; }
11  
12    // Constructor to initialize the node with a value and a next node
13    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
14}
15
16public class Solution {
17  
18    // Removes the nth node from the end of the list
19    public ListNode removeNthFromEnd(ListNode head, int n) {
20        // Create a dummy node that precedes the head of the list
21        ListNode dummyNode = new ListNode(0, head);
22      
23        // Initialize two pointers, starting at the dummy node
24        ListNode fastPointer = dummyNode;
25        ListNode slowPointer = dummyNode;
26      
27        // Move the fast pointer n steps ahead
28        while (n-- > 0) {
29            fastPointer = fastPointer.next;
30        }
31      
32        // Move both pointers until the fast pointer reaches the end of the list
33        while (fastPointer.next != null) {
34            slowPointer = slowPointer.next;
35            fastPointer = fastPointer.next;
36        }
37      
38        // Skip the node that is nth from the end
39        slowPointer.next = slowPointer.next.next;
40      
41        // Return the head of the modified list, which is the next node of dummy node
42        return dummyNode.next;
43    }
44}
45
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    // Removes the n-th node from the end of the list and returns the new head
14    ListNode* removeNthFromEnd(ListNode* head, int n) {
15        // Create a dummy node pointing to the head to handle edge cases easily
16        ListNode* dummyNode = new ListNode(0, head);
17        // These pointers will help find the node to remove
18        ListNode* fastPointer = dummyNode;
19        ListNode* slowPointer = dummyNode;
20      
21        // Move fastPointer n steps ahead
22        for(int i = 0; i < n; i++) {
23            fastPointer = fastPointer->next;
24        }
25      
26        // Move both pointers until fastPointer reaches the last node
27        while (fastPointer->next != nullptr) {
28            slowPointer = slowPointer->next;
29            fastPointer = fastPointer->next;
30        }
31      
32        // slowPointer will be just before the node we want to remove
33        slowPointer->next = slowPointer->next->next;
34      
35        // The returned head might not be the original head if the first node was removed
36        ListNode* newHead = dummyNode->next;
37        delete dummyNode; // Clean up memory used by dummyNode
38        return newHead;
39    }
40};
41
1// Type definition for a single node of a singly linked list.
2type ListNode = {
3    val: number;
4    next: ListNode | null;
5}
6
7// Function to create a new ListNode with given value and next node.
8function createListNode(val: number = 0, next: ListNode | null = null): ListNode {
9    return { val, next };
10}
11
12/**
13 * Removes the n-th node from the end of the list and returns the head of the modified list.
14 * @param {ListNode | null} head - The head of the linked list.
15 * @param {number} n - The position from the end of the list to remove the node.
16 * @returns {ListNode | null} - The head of the list after removal.
17 */
18function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
19    // Create a dummy node that will help in edge cases, like removing the first node.
20    const dummy = createListNode(0, head);
21    // Initialize two pointers, both start at the dummy node.
22    let fastPointer: ListNode | null = dummy;
23    let slowPointer: ListNode | null = dummy;
24  
25    // Advance the fast pointer n steps ahead of the slow pointer.
26    for (let i = 0; i < n; ++i) {
27        fastPointer = fastPointer.next;
28    }
29  
30    // Move both pointers until the fast pointer reaches the end of the list
31    while (fastPointer.next !== null) {
32        slowPointer = slowPointer.next;
33        fastPointer = fastPointer.next;
34    }
35  
36    // Skip the target node by assigning its next node to the next of the slow pointer.
37    // This effectively removes the target node from the list.
38    slowPointer.next = slowPointer.next.next;
39  
40    // Return the new head of the list. The dummy node's next pointer points to the list head.
41    return dummy.next;
42}
43
Not Sure What to Study? Take the 2-min Quiz：

What's the relationship between a tree and a graph?

Time and Space Complexity

The given code is designed to remove the nth node from the end of a singly linked list. It employs the two-pointer technique with fast and slow pointers. Let's analyze the time and space complexity:

Time Complexity

The time complexity is determined by the number of operations required to traverse the linked list. There are two main steps in this algorithm:

  1. The fast pointer moves n steps ahead – this takes O(n) time.
  2. Both fast and slow pointers move together until fast reaches the last node. The worst-case scenario is when n is 1, which would cause the slow pointer to traverse the entire list of size L (list length), taking O(L) time.

Since the list is traversed at most once, the overall time complexity is O(L).

Space Complexity

The space complexity is determined by the amount of additional space used by the algorithm, which does not depend on the input size:

  • The dummy node and the pointers (fast and slow) use constant extra space, regardless of the linked list's size.
  • Therefore, the space complexity is O(1) for the extra space used by the pointers and the dummy node.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫