note: the sort() method can be used to merge to sorted linked list
* 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) {
// using merge sort on the given list
return merge(head);
}
public ListNode merge(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode middleNode = findMiddleNode(head);
ListNode next = middleNode.next;
middleNode.next = null;
ListNode left = merge(head);
ListNode right = merge(next);
ListNode sortedNode = sort(left, right);
return sortedNode;
}
public ListNode sort(ListNode l, ListNode r) {
// base case
if (l == null)
return r;
else if (r == null)
return l;
ListNode result = null;
if (l.val < r.val) {
result = l;
result.next = sort(l.next, r);
} else {
result = r;
result.next = sort(l, r.next);
}
return result;
}
public ListNode findMiddleNode(ListNode head) {
if (head == null)
return head;
ListNode slow = head;
ListNode faster = head;
// 1>2>3>null
// 1>2>null
// null
while (faster.next != null && faster.next.next != null) {
slow = slow.next;
faster = faster.next.next;
}
return slow;
}
}
