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.

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!

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!

Last Updated on

Leave a Reply

Your email address will not be published. Required fields are marked *