LC19. Remove Nth Node From End of List

작성일

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

  • 링크드 리스트, 간단하게 구현하려고 걍 재귀를 썼는데, 링크드리스트는 일반적으로 1만개를 훌쩍 넘을 수 있기 때문에 바람직하지 않아보인다.
  • 이것 역시 Two-Point로 풀어야 한다. 두개의 포인터를 N개 차이로 전진시키면 간단하게 해결된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int go(ListNode* cur, ListNode* prev, int target) {
        if(!cur) return 1;
        int dist = go(cur->next, cur, target);
        
        if(dist == target)
            prev->next = cur->next;
        return dist+1;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode vroot(0);
        vroot.next = head;
        go(head, &vroot, n);
        return vroot.next;
    }
};