**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.