2015年8月27日星期四

Lintcode: Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.
Have you met this question in a real interview? 
Yes
Example
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Tags Expand 
Linked List

Solution 1:
Keep comparing current value and next node value:
If equal: link current node to the next next node and delete next node;
If not equal: jump to next node

Time: O(n)
Space: O(1)


 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
/**
 * 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.
     * @return: head node
     */
    ListNode *deleteDuplicates(ListNode *head) {
        // write your code here
       if(head == NULL) return NULL;
       ListNode *cur = head;
       while(cur->next != NULL){
           if(cur->next->val == cur->val) {
               ListNode *temp = cur->next;
               cur->next = cur->next->next;
               delete temp;
           }
           else cur = cur->next;
       }
       return head;      
    }
};

Solution 2: two pointers
left pointer is at the start of repetition while right pinter is at the end.
Note: the right pointer may point to NULL and don't forget to delete node
Time: O(n)
Space: O(1)
 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
/**
 * 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.
     * @return: head node
     */
    ListNode *deleteDuplicates(ListNode *head) {
        // write your code here
       if(head == NULL) return NULL;
       ListNode *left, *right;
       left = head;
       right = left->next;
       while(right!= NULL){
           while(left->val == right->val){
               //if(right->next != NULL){
                    ListNode *temp = right;
                    right = right->next;
                    delete temp;
                    if(right == NULL){
                        left->next = right;
                        return head;
                    }
                    else if(left->val != right->val){
                        left->next = right;
                        break;
                    }
           }
           left = left->next;
           right = right->next;
       }
       return head;
    }
};


Lintcode second:
O(n) two pointers


 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
/**
 * 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.
     * @return: head node
     */
    ListNode *deleteDuplicates(ListNode *head) {
        // write your code here
        ListNode *start, *end;
        start = end = head;
        
        while(start){
            //end is located at the point that is equal to start
            while(end && end->next && end->next->val == start->val){
                end = end->next;
            }
            if(start != end) start->next = end->next;
            start = start->next;
            end = start;
        }
        return head;
    }
};
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)