2015年8月26日星期三

Lintcode: Merge Two Sorted Lists

Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splicing together the nodes of the two lists and sorted in ascending order.
Have you met this question in a real interview? 
Yes
Example
Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null.
Tags Expand 
Linked List


My solution:
Create a new linkedlist with a dummy node:
Compare elements from two lists, only add the smaller one into my linkedlist until either one is null.
Note: Take notice of linking nodes with the next pointer.
Time: O(m+n)
Space: O(m+n)
Analysis: It's not necessary to create new Node, just link the existing nodes into one linkedlist is enough.

 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
49
50
51
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        ListNode *result = new ListNode(0);
        ListNode *cur = result;
        ListNode *left, *right;
        left = l1;
        right = l2;
        while(left!=NULL && right!=NULL){
            if(left->val < right->val) {
                cur->next = new ListNode(left->val);
                cur = cur->next;
                left = left->next;
            }
            else{
                cur->next = new ListNode(right->val);
                cur = cur->next;
                right = right->next;
            }
        }
        while(left!=NULL){
            cur->next = new ListNode(left->val);
            left = left->next;
            cur = cur->next;
        }
        while(right!=NULL){
            cur->next = new ListNode(right->val);
            right = right->next;
            cur = cur->next;
        }
        return result->next;
    }
};

Common solution:
Good version to reference:
http://shibaili.blogspot.com/2013/04/day-12-21-merge-two-sorted-lists.html
Note: Dummy node is important when the head pointer is unsure.


 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 ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        ListNode *head = new ListNode(0);
        ListNode *cur = head;
        while(true){
            if(l1 == NULL){
                cur->next = l2;
                break;
            }
            if(l2 == NULL){
                cur->next = l1;
                break;
            }
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        return head->next;
    }
};

Lintcode second:
O(n) dummy 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
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param ListNode l1 is the head of the linked list
     * @param ListNode l2 is the head of the linked list
     * @return: ListNode head of linked list
     */
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        // write your code here
        
        ListNode *head = new ListNode(0);
        ListNode *orghead = head;
        while(l1 && l2){
            if(l1->val < l2->val){
                head->next = l1;
                l1 = l1->next;
            }else{
                head->next = l2;
                l2 = l2->next;
            }
            head = head->next; //don't forget...
        }
        if(l1) head->next = l1;
        if(l2) head->next = l2;
        return orghead->next;
    }
};
发帖者 时间：

没有评论:

发表评论

订阅： 博文评论 (Atom)