Sort List

	Total Accepted: 2517 Total Submissions: 13801 My Submissions
	Sort a linked list in O(n log n) time using constant space complexity.
	Do it like merge sort for array, pay attention to how to find the middle
	/**
	* 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) {
	if (head==null||head.next==null){
	return head;
	}
	ListNode fast=head;
	ListNode slow=head;
	while(fast.next!=null&&fast.next.next!=null){
	fast=fast.next.next;
	slow=slow.next;
	}
	ListNode right=slow.next;
	slow.next=null;
	head=sortList(head);
	right=sortList(right);
	return merge(head, right);
	}
	private ListNode merge(ListNode n1, ListNode n2){
	if (n1==null) return n2;
	if (n2==null) return n1;
	ListNode head=null;
	ListNode end=null;
	while(n1!=null && n2!=null){
	ListNode current=null;
	if (n1.val<n2.val){
	current=n1;
	n1=n1.next;
	}
	else{
	current=n2;
	n2=n2.next;
	}
	if (head==null){
	head=current;
	end=head;
	continue;
	}
	end.next=current;
	end=end.next;
	}
	if (n1==null){
	end.next=n2;
	}
	if (n2==null){
	end.next=n1;
	}
	return head;
	}
	}

view raw Sort List.java hosted with ❤ by GitHub