The below java program manages to do it within the same complexity limit.
If you see the code, we are dividing the LinkedList in halves with each recursive call. So recursion tree height would be log n. For each of these recursive step, we are finding the middle element of the current linked list which requires a full traversal. So it would be O(n). And we are merging sub lists in each recursive step which will again take O(n) (our merge() method is linear complexity). So worst case time complexity is (n + n) * log n = O(n logn).
Regarding space complexity, I am not creating any additional Linked List for merging and doing the merge in place by changing the pointers. Only four additional variables are used in merge step and that is fixed. So if we omit the space taken by recursion stack, we are using constant space. So space complexity is O(1).
/** * 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) { return mergeSort(head); } public ListNode mergeSort(ListNode head){ if(head == null || head.next == null){ return head; } ListNode middle = findMiddle(head); ListNode nextToMiddle = middle.next; middle.next = null; //sort left hand side array ListNode leftHead = mergeSort(head); //sort right hand side array ListNode rightHead = mergeSort(nextToMiddle); return merge(leftHead, rightHead); } public ListNode merge(ListNode left, ListNode right){ ListNode dummyHead = new ListNode(0); ListNode tail = dummyHead; ListNode leftTemp = left; ListNode rightTemp = right; int count = 0; while(leftTemp != null && rightTemp != null){ if(leftTemp.val <= rightTemp.val){ tail.next = leftTemp; leftTemp = leftTemp.next; } else { tail.next = rightTemp; rightTemp = rightTemp.next; } tail = tail.next; } if(leftTemp == null){ tail.next = rightTemp; } else { tail.next = leftTemp; } return dummyHead.next; } public ListNode findMiddle(ListNode head){ ListNode slow = head; ListNode fast = head; while(fast.next != null && fast.next.next != null){ slow = slow.next; fast = fast.next.next; } return slow; } }
No comments:
Post a comment