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.