首页 > 代码库 > LeetCode Solutions : Sort List

LeetCode Solutions : Sort List

【题目描述】Sort a linked list in O(n log n) time using constant space complexity.

【算法思路】时间复杂度限制在O(n log n),我们可以第一时间想到常用的二路归并排序,快速排序和堆排序,其中快排和堆排只适用于线性表,即数组,故这道编程题毫无疑问用二路归并排序;

【编程步骤】

 * 1. 利用一个小技巧,可以设置慢行指针low和快行指针fast,把链表分成两部分来操作,即first和second链表
 * 2. 递归排序first和second链表,即

first=sortList(head);
second=sortList(second);

 * 3. 合并这两个链表,即:mergeListSort(first,second)

代码实现:

/**
 * 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 second=slow.next;
		slow.next=null;
		ListNode first=sortList(head);
		second=sortList(second);
		return mergeListSort(first,second);
    }
	private ListNode mergeListSort(ListNode first,ListNode second){
		ListNode newList=new ListNode(0);
		ListNode p=newList;
		while(first!=null&&second!=null){
			if(first.val<=second.val){
				p.next=first;
				first=first.next;
			}else{
				p.next=second;
				second=second.next;
			}
			p=p.next;
		}
		if(first!=null)
			p.next=first;
		if(second!=null)
			p.next=second;
		return newList.next;
	}	
}


LeetCode Solutions : Sort List