LeetCode: Remove Nth Node From End of List

LeetCode: Remove Nth Node From End of List 1
\(\)

Leetcode Problem

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.

Explanation

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;
  }
};

Preparing for an interview? Check out this!

Don't miss out!
Subscribe To Newsletter

Want to be better at coding and CS ?

Programming tutorials

Career advice and tips

......

It's Free!

Invalid email address
Last Updated on

Leave a Reply

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