Sort a linked list in O(n log n) time using constant space complexity.
Method 1: This code can be accepted by leetcode online judge. The code is the implementation of the meger sort idea.
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
ListNode newHead = null;
int length = 0;
if(head != null){
newHead = head;
ListNode nextNode = head;
while(nextNode != null){
++length;
nextNode = nextNode.next;
}
if(length > 1){
int rank = 1;
while(rank < length){
ListNode temp = sortListHelper(newHead, rank);
newHead = temp;
rank *= 2;
}
}
}
return newHead;
}
public static ListNode sortListHelper(ListNode head, int n){
ListNode start = head;
PairNodes sortedList = null;
while(start != null){
ListNode start1 = start;
PairNodes splits = splitNodes(start1, n);
ListNode firstNode = start;
ListNode secondNode = null;
if(splits.head != null)
secondNode = splits.head;
PairNodes partialSorted = mergeNodes(firstNode, secondNode);
if(sortedList == null)
sortedList = partialSorted;
else{
sortedList.tail.next = partialSorted.head;
sortedList.tail = partialSorted.tail;
}
start = splits.tail;
}
return sortedList.head;
}
public static PairNodes splitNodes(ListNode start, int n){
PairNodes splits = new PairNodes();
splits.head = null;
splits.tail = null;
int i = 1;
while(start != null && i < 2*n){
if(i == n){
splits.head = start.next;
start.next = null;
start = splits.head;
}
else
start = start.next;
++i;
}
if(start != null){
splits.tail = start.next;
start.next = null;
}
return splits;
}
public static PairNodes mergeNodes(ListNode firstNode, ListNode secondNode){
PairNodes result = new PairNodes();
if(firstNode != null || secondNode != null){
if((firstNode == null && secondNode != null) ||(firstNode != null && secondNode == null)){
ListNode start = (firstNode == null) ? secondNode : firstNode;
result.head = start;
while(start.next != null)
start = start.next;
result.tail = start;
}
else{
ListNode mini = new ListNode(0);
ListNode current = mini;
while(firstNode != null && secondNode != null){
if(firstNode.val > secondNode.val){
ListNode temp = firstNode;
firstNode = secondNode;
secondNode = temp;
}
current.next = firstNode;
current = current.next;
if(firstNode.next == null)
break;
else
firstNode = firstNode.next;
}
firstNode.next = secondNode;
while(firstNode.next != null)
firstNode = firstNode.next;
result.head = mini.next;
result.tail = firstNode;
}
}
return result;
}
}
class PairNodes{
ListNode head;
ListNode tail;
PairNodes(){};
}
Method 2:
The following code is correct and satifies all requirement. But it can not be accepted by leetcode online judge because the recursive calling incurs a java.lang.StackOverflowError.
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode sortList(ListNode head) {
ListNode newHead = null;
int length = 0;
if(head != null){
newHead = head;
ListNode nextNode = head;
while(nextNode != null){
++length;
nextNode = nextNode.next;
}
if(length > 1){
int rank = 1;
while(rank < length){
ListNode temp = sortListHelper(newHead, rank, length);
newHead = temp;
rank *= 2;
}
}
}
return newHead;
}
public ListNode sortListHelper(ListNode head, int rank, int length){
ListNode result = head;
ListNode firstNode = head;
ListNode secondNode = head;
ListNode thirdNode = null;
ListNode newHead = head;
if(rank < length){
int i = 1;
while(newHead != null && i < 2 * rank){
if(i == rank){
secondNode = newHead.next;
newHead.next = null;
newHead = secondNode;
}
else
newHead = newHead.next;
++i;
}
if(newHead != null){
thirdNode = newHead.next;
newHead.next = null;
}
if(firstNode.val > secondNode.val){
ListNode temp = firstNode;
firstNode = secondNode;
secondNode = temp;
}
ListNode mini = new ListNode(0);
ListNode current = mini;
while(firstNode != null && secondNode != null){
if(firstNode.val > secondNode.val){
ListNode temp = firstNode;
firstNode = secondNode;
secondNode = temp;
}
current.next = firstNode;
current = current.next;
if(firstNode.next == null)
break;
else
firstNode = firstNode.next;
}
if(secondNode != null)
firstNode.next = secondNode;
while(firstNode.next !=null)
firstNode = firstNode.next;
result = mini.next;
length -= i;
if(thirdNode != null)
firstNode.next = sortListHelper(thirdNode, rank, length);
else
firstNode.next = null;
}
return result;
}
}