Skip to content

19. Remove Nth Node From End of List

Source: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Intuition

Naive Solution: Use len−nlen - n pass recursion.

  • Get the length of the linked list
  • calculate the removal position
  • Use recursion version of removal function
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int key = length(head) - n + 1;
        return removeNthFromStart(head, key);
    }

    private int length(ListNode head) {
        int size = 0;
        while (head != null) {
            size++;
            head = head.next;
        }
        return size;
    }

    private ListNode removeNthFromStart(ListNode head, int n) {
        if (n == 1) {
            return head.next;
        }
        return new ListNode(head.val, removeNthFromStart(head.next, n - 1));
    }
}

Approach

  • Calculate the length of linked list
  • Traverse the linked list using loop, when arrive the removal position, simply jump to the next node.
  • Get removed linked list.

Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode memo = null;
        int size = 0;
        int count = 0;
        while (head != null) {
            size++;
            memo = new ListNode(head.val, memo);
            head = head.next;
        }
        while (size > 0) {
            count++;
            if (count == n) {
                memo = memo.next;
                size--;
                continue;
            }
            head = new ListNode(memo.val, head);
            memo = memo.next;
            size--;
        }
        return head;
    }
}