Leetcode 21 Merge Two Sorted Lists and 148 Sort List

Leetcode 21 Merge Two Sorted Lists and 148 Sort List

Leetcode 21 Merge Two Sorted Lists
Edit Merge Two Sorted Lists on GitHub

The problem description is as follow:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

Alright, you hear the man. Don’t create a new list and assign values, instead we should splice the original two lists and merge them.

I decide to merge second list to first list:
1. Create a dummy list header, point it to the head of first list.
2. Compare the first nodes' value in first list and second list.
3. If value of list 2 is smaller, merge it to list 1; If value of list 1 is smaller, move to the next larger value in list 1 and keep comparing.

Note that there will be two different situations at the end:

1. If list 1 runs out of node first, that means remaining nodes in list 2 are all larger than the largest in list 1. Append the remaining to the end of dummy list.
2. If list 2 runs out of node first, that means sorting is over, merge complete.

Here comes the code:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode helper = new ListNode(0);
        ListNode pre = helper;
        helper.next = l1;
        while(l1!=null && l2 != null){
            if(l1.val>l2.val){
                ListNode next = l2.next;
                l2.next = pre.next;
                pre.next = l2;
                l2 = next;
            }
            else{
                l1 = l1.next;
            }
            pre = pre.next;
    
        }
        if(l2!=null){
            pre.next = l2;
        }
        return helper.next;
    }
}

If length of first list is m, length of second list is n, the time complexity will be O(m+n). The extra space we need will be O(1) for the dummy header ListNode helper = new ListNode(0)

Leetcode 148 Sort List
Edit Sort List on GitHub

The problem description is as follow:

Sort a linked list in O(n log n) time using constant space complexity.
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

This problem we can solve it the famous merge-sort. The main thought behind this algorithm is divide and conquer:

1. Divide the original list into 2.
2. Sort the 2 separate lists.
      (Recursive)
    - Divide list 1 into 2.
    - Sort those 2 separate lists.
    - Merge those 2 separate lists.
      (Recursive)
    - Divide list 2 into 2.
    - Sort those 2 separate lists.
    - Merge those 2 separate lists.
3. Merge the 2 separate lists into 1.

Here comes the code:

public class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    private ListNode mergeSort(ListNode head){
        if(head == null || head.next == null)
            return head;
        // find middle of list
        ListNode walker = head;
        ListNode runner = head;
        while(runner.next!=null && runner.next.next!=null){
            walker = walker.next;
            runner = runner.next.next;
        }
        //break original list into two
        ListNode head2 = walker.next;
        walker.next = null;
        ListNode head1 = head;
        //recursive call
        head1 = mergeSort(head1);
        head2 = mergeSort(head2);
        return merge(head1, head2);
    }
    private ListNode merge(ListNode head1, ListNode head2){
        ListNode helper = new ListNode(0);
        helper.next = head1;
        ListNode pre = helper;
        while(head1!=null && head2!=null){
            if(head1.val<head2.val){
                head1 = head1.next;
            }
            else{
                ListNode next = head2.next;
                head2.next = pre.next;
                pre.next = head2;
                head2 = next;
            }
            pre = pre.next;
        }
        // head1 is null, append head2 to the end of the list
        if(head2!=null)
        {
            pre.next = head2;
        }
        // if head2 is null and head1 is not, that means sorting is over,
        // need not to do anything
        return helper.next;
    }
}

As you can see, the merge process is exactly the same as our previous problem Merge Two Sorted Lists. Now let’s consider the time complexity:

Assume the length of original list is n, the time complexity is function T(n), then we have T(n) = T(n/2) + O(n).

O(n) is the time to merge two sorted lists of length  n/2.

According to Master Theorem,  T(n) = O(n logn)

The space complexity is  O(logn), which is the depth of our recursive call.