remove-nth-node-from-end-of-list

gistfile1.txt

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

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

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
 /*
 testcase
 {1}, 1
 {0,1}, 1
 {0,1,2} 2
 별다른 어려움없이 runner 2개 이용하여 첫번째와 두번째를 k간격 만큼 띄운다음,
 두번째 runner가 Null을 가리킬따까지 shift한다. 그때 첫번째  runner가 가리키는 다음 노드를 지우고 붙이면된다.
 
 주의할점은 k가 linkedlist의 length보다 작거나 '같은' 값이므로 edge 처리를 잘해야한다.
 
 single linkedlist는 언제나 해당값의 바로 앞 노드까지 runner를 이동해서 ->next로 접근 해야함(->prev가 없으므로)

 */
 
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        if(n <= 0 || head == NULL) return head;
        
        ListNode* cur = head;
        ListNode* kPointer = head;
        
        for(int i=0; i<n; i++) kPointer = kPointer->next;    
        
        if(kPointer == NULL) { //1번째 노드를 지우는 경우
            head = cur->next;
            
            delete cur;
        } else {
            while(kPointer->next != NULL) {
                cur = cur->next;
                kPointer = kPointer->next; 
            }
            
            ListNode* remove = cur->next;
            cur->next = cur->next->next;
            delete remove;
        }
        
        return head;  
    }
};