Posts Merge Sort Linked List
Post
Cancel

Merge Sort Linked List

PROBLEM DESCRIPTION

Merge Sort a given Linked List.

SOLUTION

snapshot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static Node mergeSort(Node h1){

    if(h1 == null || h1.next == null) return h1;

    Node c1 = getCenter(h1);
    Node h2 = c1.next;
    c1.next = null;

    h1 = mergeSort(h1);
    h2 = mergeSort(h2);

    return mergeSortedLinkedList(h1, h2);

}

Complete code: https://leetcode.com/problems/sort-list/

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode c1 = getCenter(head);
        ListNode h2 = c1.next;
        c1.next = null;

        head = sortList(head);
        h2 = sortList(h2);

        return mergeSortedLinkedList(head, h2);
    }
    

    
    public static ListNode getCenter(ListNode head){

        ListNode s=head;
        ListNode f=head;

        while(f.next != null && f.next.next != null){
            s = s.next;
            f = f.next.next;
        }

        return s;

    }
    
    public static ListNode mergeSortedLinkedList(ListNode h1, ListNode h2){

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

        ListNode t=null, h3=null;

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

        
        while(h1 != null && h2 != null){
            if(h1.val < h2.val){
                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;
    }
}
This post is licensed under CC BY 4.0 by the author.