LeetCode #19: Remove Nth Node From End of List (C/C++).

medium

source: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
C/C++ Solution to LeetCode problem 19. Remove Nth Node From End of List.

Problem

---

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

Examples

---

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,4,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints

---

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Solution

---

We will use a variation of the “Tortoise and Hare” (Floyd’s) algorithm that is used to find cycles in a list of nodes.

• We initialize two pointer at the head node.
• We move one of them n times.
• Then we start moving both at the same time, when the firstone arrives to the end node (when pointer_1->next == nullptr) then we know that the second pointer is right before the node we want to delete.
• Then we just re-assign the pointer_2->next to pointer_1_node->next->next.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
      ListNode* p1 = head;
      ListNode* p2 = head;

      int i=0;
      while (p1->next && i<n) {
        p1 = p1->next;
        i++;
      }
      if (i<n)
        return head->next;

      while(p1->next) {
        p1 = p1->next;
        p2 = p2->next;
      }

      p2->next = p2->next->next;

      return head;
    }
};