2015年8月26日星期三

Lintcode: Remove Nth Node From End of List


Given a linked list, remove the nth node from the end of list and return its head.
Have you met this question in a real interview? 
Yes
Example
Given linked list: 1->2->3->4->5->null, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5->null.
Note
The minimum number of nodes in list is n.
Challenge
O(n) time
Tags Expand 
Two Pointers Linked List


Note: consider special case that when the nth node from the end is head;
Both ways have the same complexity:
Time: O(n)
Space: O(1)


<way 1>
Get the length of linked lists.
Then use two pointers to delete the len - n node

 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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        int len = 0;
        ListNode * temp = head;
        while(temp){
            temp = temp -> next;
            len++;
        }
        ListNode *p;
        ListNode *q;
        p=head;
        q=p;
        int times = len - n;
        while(times > 0){
            q = p;
            p = p -> next;
            times--;
        }
        if(len == n){
            q = p->next;
            delete head;
            return q;
        }
        temp = p -> next;
        delete p;
        q->next = temp;
        return head;
    }
};


<way 2> common two pointers solution
Set two pointers n nodes far away from each other. Move the front one forward until null, then the back one is located at the node we wanna delete.


 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
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        ListNode *slow;
        ListNode *fast;
        slow = head;
        fast = head;
        for(int i = 0; i < n; i++){
            fast = fast -> next;   
        }
        ListNode *prev = slow;
        //special case, when the element to be deleted is head
        if(!fast){
            slow = slow -> next;
            delete head;
            return slow;
        }
        while(fast){
            prev = slow;
            slow = slow -> next;
            fast = fast -> next;
        }
        ListNode *temp = slow -> next;
        delete slow;
        prev -> next = temp;
        return head;
    }
};

Lintcode second:
two pointers, O(n), remember when delete head,return new 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
35
36
37
38
39
40
41
42
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer.
     * @return: The head of linked list.
     */
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        // write your code here
        ListNode *p1, *p2;
        p1 = p2 = head;
        for(int i = 0; i < n; i++){
            p2 = p2->next;
        }
        ListNode *prev;
        while(p2){
            p2 = p2->next;
            prev = p1;
            p1 = p1->next;
        }
        if(p1 == head) {
            ListNode *res = p1->next;
            delete head;
            return res;
        }
        prev->next = p1->next;
        delete p1;
        return head;
    }
};
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)