By Long Luo

This article is the solution 3 Approaches: Brute Force, Stack, Slow Fast Pointers with Animation of Problem 19. Remove Nth Node From End of List.

Here shows 3 Approaches to slove this problem: Brute Force, Stack, Slow Fast Pointers.

Brute Froce

It’s easy to think of the way that we traverse the linked list first, from the head node to the end node, to get the length of the linked list \(L\).

Then we traverse the linked list from the head node again. When the \(L-n+1\) th node is traversed, it is the node we need to delete.

We can traverse \(L-n+1\) nodes starting from the dummy node. When traversing to the \(L-n+1\)th node, its next node is the node we need to delete, so we only need to modify the pointer once to complete the deletion operation.

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

public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head.next == null && n == 1) {
        return null;
    }

    List<ListNode> nodeList = new ArrayList<>();
    ListNode pNode = head;
    int size = 0;
    while (pNode != null) {
        nodeList.add(pNode);
        size++;
        pNode = pNode.next;
    }

    if (n == size) {
        return head.next;
    } else if (n == 1) {
        pNode = nodeList.get(size - 2);
        pNode.next = null;
    } else {
        pNode = nodeList.get(size - n - 1);
        pNode.next = pNode.next.next;
    }

    return head;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

Stack

We can also push all nodes on the stack one by one while traversing the linked list.

As the stack is FILO, the nth node we pop out of the stack is the node that needs to be deleted, and the node at the top of the stack is the predecessor node of the node to be deleted.

In this way, the deletion operation becomes very convenient.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head.next == null && n == 1) {
        return null;
    }

    Stack<ListNode> stack = new Stack<>();
    ListNode dummyNode = new ListNode(-1);
    dummyNode.next = head;
    ListNode pNode = dummyNode;
    while (pNode != null) {
        stack.push(pNode);
        pNode = pNode.next;
    }

    while (n > 0) {
        stack.pop();
        n--;
    }

    pNode = stack.peek();
    pNode.next = pNode.next.next;
    return dummyNode.next;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

Slow Fast Pointers

1. Set \(dummyHead\) to point to head node;
2. Set the two pointers \(slow\) and \(fast\), point to the node \(dummyHead\);
3. Move \(fast\) until the number of elements between \(slow\) and \(fast\) is \(n\);
4. Move both \(slow\) and \(fast\) until \(fast\) points to \(NULL\);
5. Point the next node of \(slow\) to the next node.

As the animation shows below:

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

public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head.next == null && n == 1) {
        return null;
    }

    ListNode dummyNode = new ListNode(-1);
    ListNode preNode = dummyNode;
    dummyNode.next = head;

    ListNode fast = head;
    for (int i = 1; i < n; i++) {
        fast = fast.next;
    }

    ListNode slow = head;
    while (fast.next != null) {
        fast = fast.next;
        preNode = preNode.next;
        slow = slow.next;
    }

    preNode.next = slow.next;

    return dummyNode.next;
}

Analysis

• Time Complexity: \(O(n)\), \(n\) is the length of the linked list.
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗