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.

/**
* 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)`

The problem description is as follow:

```Sort a linked list in O(n log n) time using constant space complexity.
/**
* 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 {
}
// find middle of list
while(runner.next!=null && runner.next.next!=null){
walker = walker.next;
runner = runner.next.next;
}
//break original list into two
walker.next = null;
//recursive call
}
ListNode helper = new ListNode(0);
ListNode pre = helper;
}
else{
}
pre = pre.next;
}
// head1 is null, append head2 to the end of the list
{
}
// 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.