Posts Merge Two Sorted Linked List - 2
Post
Cancel

Merge Two Sorted Linked List - 2

PROBLEM DESCRIPTION

Merge two sorted Linked List.

leetcode

SOLUTION

snapshot

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
public static Node mergeSortedLinkedList(Node h1, Node h2){

    //If any of the list is empty, return the other sorted list
    if(h1 == null) return h2;
    if(h2 == null) return h1;

    Node t=null, h3=null;

    //Initialize
    if(h1.value < h2.value){
        t=h1;
        h3=h1;
        h1=t.next;
    }else{
        t=h2;
        h3=h2;
        h2=t.next;
    }


    while(h1 != null && h2 != null){
        if(h1.value < h2.value){
            t.next=h1;
            h1=h1.next;
            t=t.next;
        }else{
            t.next=h2;
            h2=h2.next;
            t=t.next;
        }
    }

    if(h1 == null){
        t.next = h2;
    }else{
        t.next = h1;
    }

    return h3;
}

RECURSIVE SOLUTION

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
class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1 == null && list2 == null) return null;
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode h1=list1;
        ListNode h2=list2;

        ListNode h3;

        if(h1.val <= h2.val){
            h3=h1;
            ListNode t = h1.next;
            h1.next = mergeTwoLists(t, h2);
        }else{
            h3=h2;
            ListNode t = h2.next;
            h2.next = mergeTwoLists(h1, t);
        }

        return h3;

    }

}

BETTER RECURSIVE CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        if(list1 == null)
            return list2;

        if(list2 == null)
            return list1;

        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }

    }

}

ANOTHER WAY TO CODE USING DUMMY 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
class Solution {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        ListNode dummyHead = new ListNode(0);

        ListNode temp = dummyHead;

        while(list1 != null && list2 != null){

            int x = list1.val;
            int y = list2.val;

            if(x<y){
                temp.next = list1;
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2 = list2.next;
            }

            temp = temp.next;

        }

        if(list1 != null){
            temp.next = list1;
        }else{
            temp.next = list2;
        }

        return dummyHead.next;

    }

}
This post is licensed under CC BY 4.0 by the author.