LeetCode: Remove Nth Node From End of List

Description

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid.

Naive solution

First, we need to get the length of the link list, the time complexity will be $O(N)$, we can not avoid this step, so this is also the best time complexity.

Given the length of link list, remove the n-th node will be easy if we find the node at pos length-n.

Note a dummy node will make the code cleaner.

file:img/CAPTURE-2019_12_24_remove-nth-node-from-end-of-list.org_20191224_112700.png

class Solution {
public:
  ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* cur = head;
    int len = 0;
    while(cur) {
      cur = cur->next;
      len++;
    }
    len -= n;
    cur = dummy;
    while(len > 0) {
      cur = cur->next;
      len--;
    }
    cur->next = cur->next->next;
    return dummy->next;
  }
};

Approach with two pointers

This is a clever approach, if we use two pivot pointers, their distance is n+1. Then if we move the tail forward to the end of linklist, the prev will be the pointer whose next can be deleted!

file:img/2019_12_24_remove-nth-node-from-end-of-list.org_20200204_230523.png

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode root(0);
        root.next = head;
        ListNode* prev = &root;
        ListNode* tail = head;

        while(n--) tail = tail->next;
        
        while (tail){
            tail = tail->next;
            prev = prev->next;
        }
        
        prev->next = prev->next->next;
          return root.next;
    }
};

Preparing for an interview? Check out this!

← How To Learn Data Structures And... Leetcode: Longest Common Prefix →