[LeetCode] 19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

Remove Nth Node From End of List - LeetCode

Leetcode - Remove Nth Node From End of List

문제 유형 : 연결리스트, 투포인터

문제 난이도 : Medium

 

문제

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

연결리스트의 헤드가 주어진다. 연결리스트의 뒤에서 n번째 노드를 삭제하고 헤드를 반환하라.

 

풀이

투 포인터를 이용하면 된다.

ListNode* left와 right를 head로 선언하고, right는 먼저 n칸 이동시킨다. 이러면 서로 n칸 차이가 난다.

간격을 유지하면서 최대한 끝으로 보내고 나면, left의 다음 노드가 지워야 할 노드이다.

만약 먼저 이동하고나서 right가 null을 가리킨다면, 첫 번째 노드를 삭제하라는 뜻이므로 head -> next를 반환한다.

right이 마지막 노드에 도달할 때 까지 left와 right를 다음으로 계속 이동시킨다.

left의 next를 연결리스트에서 삭제하면 된다.

 

이외에도 스택이나 재귀를 이용한 풀이도 가능하다.

코드

C++

/**
 * 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) {
        auto right = head;
        auto left = head;

        for (int i = 0; i < n; i++) {
            right = right->next;
        }
        
        if (right == nullptr) {
            return head->next;
        }
        
        while (right->next) {
            right = right->next;
            left = left->next;
        }
        
        left->next = left->next->next;
        
        return head;
    }
};