Remove Nth Node From End of List[M,Linked List,Two Pointers]

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

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?

 

1. C

뭔가 풀긴했는데, 좀 조잡하다.

Test case 통과 못한 것을 실시간으로 보면서 풀었기때문에 풀었지,

Test case가 뭔지 모르는 경우엔 해답 찾기가 쉽지 않은 접근이다.

Edge Case를 한 번에 체크할 수 있는 방법이 뭐가 있을까나..

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    if(!head || !head->next) return NULL;

    struct ListNode* fast = head;
    struct ListNode* slow = head;
    struct ListNode* prev = head;
    int cnt = 0;

    while(fast){
        fast = fast->next;
        if(cnt>=n){
            prev = slow;
            slow = slow->next;
        }
        cnt++;
    }
    if(prev==slow) return prev->next;

    prev->next = slow -> next;
    return head;
}

 

사람 생각이 다 비슷한가보다.

다른 사람들 Solution도 아래와 같다. 메카니즘은 비슷

//C 끝에서 n번째 Node를 찾는 방법이 약간 다르다.
//cnt를 쓰지 않고, 미리 n만큼 node를 던져 놓고, 추가 node를 만든 뒤에 while로 끝까지 돌린다.
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode* EndNode = head;
    struct ListNode* NthNode = head;
    struct ListNode* NthPreNode = NULL;
    while (n > 0) {
        n--;
        EndNode = EndNode->next;
    }
    while (EndNode != NULL) {
        EndNode = EndNode->next;
        NthPreNode = NthNode;
        NthNode = NthNode->next;
    }
    if(NthNode == head) {
        head = head->next;
        free(NthNode);
    }
    else {

            NthPreNode->next = NthPreNode->next->next;
            free(NthNode);

    }
    return head;
}

 

2. 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) {
        ListNode* fast = head;
        ListNode* slow = head;
        ListNode* prev = nullptr;

        while(n>0){
            n--;
            fast = fast->next;
        }
        while(fast){
            fast = fast->next;
            prev = slow;
            slow = slow->next;
        }
        if(slow == head){
            return head->next;
        }
        else{
            prev -> next = prev->next->next;
            slow->next = nullptr;
            delete slow;
        }
        return head;
    }
};

 

3. Python

 

 dummy node를 이용해보기

prev도 만들지 않았다.

 

#Python - > Dummy Node를 이용해보기 / prev을 이용하지 않고 한 칸 띄어서 생각헌다
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(999);
        dummy.next = head
        
        first = dummy
        second = dummy

        for i in range(n+1):
            first = first.next
        while first:
            first = first.next
            second = second.next
        
        second.next = second.next.next

        return dummy.next

 

참고로 C++로도 dummy 만들어 주기 가능하긴 허다..

 

/**
 * 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(999);
        ListNode* ptr = &dummy;
        ptr->next = head;
        ListNode* fast = ptr;
        ListNode* slow = ptr;
        // ListNode* prev = nullptr;
        while(n>=0){
            n--;
            fast = fast->next;
        }
        while(fast){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return ptr->next;
    }
};