Remove Nth Node From End of List
Post
Cancel

# 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 /** * 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; } };