2016年2月19日 星期五

LEET code -- 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.


紀錄第n次的前一個是誰
要注意邊界問題
可能只有一個element
跟要移除的是head


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode * latter=head,*previous=head,*target=head;;
    int counter=0;
    while(latter!=NULL){
        
        if(counter>=n+1)previous=previous->next;
        if(counter>=n)target=target->next;
        counter++;
        latter=latter->next;
    }
    
    struct ListNode *temp=previous->next;
    if(temp==NULL){
        //only 1 element
        free(previous);
        return NULL;
    }else if(target==previous){
        //previous not moveing
        head=previous->next;
        free(previous);
        return head;
    }
    previous->next= temp->next==NULL? NULL:temp->next ;
    free(temp);
    
    return head;
}



-----------
比較漂亮的版本




 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    struct ListNode * latter=head,*previous=head,*target=head,*temp=NULL;;
    while(n!=0 && latter!=NULL){
        latter=latter->next;
        n--;
    }
    while(latter!=NULL){
        previous=target;
        target=target->next;
        latter=latter->next;
    }
    
    if(previous==target){
        //1 element or remove head
        temp=previous;
        head=head->next;
    }else{
        temp=target;
        previous->next=target->next;
    }
    free(temp);
    
    return head;
}

張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)