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.

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,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?

Analsysis & Solutions

• from prevNode to nextNode 의 GAP이 n이라고 가정
• prevNode가 끝까지 도착했을 때, nextNode는 맨 마지막 -n만큼에 위치하게 되므로, 이 때 노드의 연결을 변경해 준다

Code

/**
 * 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* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prevNode = dummy;
        ListNode* nextNode = dummy;

        for (int i = 0; i <= n; ++i) {
            prevNode = prevNode->next;
        }

        while (prevNode != nullptr) {
            prevNode = prevNode->next;
            nextNode = nextNode->next;
        }

        ListNode* temp = nextNode->next;
        nextNode->next = nextNode->next->next;
        delete temp;

        return dummy->next;
    }
};

Reference

[1] https://leetcode.com/problems/remove-nth-node-from-end-of-list/