【LeetCode】 sort list 单链表的归并排序

题目:Sort a linked list in O(n log n) time using constant space complexity.

思路:要求时间复杂度O(nlogn)

知识点:归并排序,链表找到中点的方法

存在的缺点:边界条件多考虑!!!

/**
 * LeetCode Sort List  Sort a linked list in O(n log n) time using constant space complexity.
 * 题目:将一个单链表进行排序,时间复杂度要求为o(nlogn)
 * 思路:1时间复杂度为o(nlog n)的排序算法有:归并排序、快排(期望)、堆排序
 * 		2、单链表排序用归并排序,双链表排序用快排
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */ 
   
package javaTrain;

class ListNode {
	     int val;
	     ListNode next;
	     ListNode(int x) {
	         val = x;
	         next = null;
	     }
}
public class Train4 { 
	public ListNode sortList(ListNode head) {
		if(head == null || head.next == null)
			return head;
		ListNode fast = head;
		ListNode slow = head;
		while(fast.next.next != null && slow.next != null){
			fast = fast.next.next;		//使得当遍历完该链表之后一个指向中间一个指向末尾,即找到链表中点
			slow = slow.next;	
		}
		ListNode list2 = slow.next;
		slow.next = null;
		head = sortList(head);
		list2 = sortList(list2);
		return merge(head,list2);
}
	private static ListNode merge(ListNode list1,ListNode list2){
		if(list1 == null) return list2;
		if(list2 == null) return list1;
		ListNode head = new ListNode(0);
		ListNode last = head; 
		while(list1.next != null && list2.next != null){
			if(list1.val <= list2.val){
				last.next = list1;
				list1 = list1.next;
			}
			else{
				last.next = list2;
				list2 = list2.next;
			}
			last = last.next;
		}
		if(list1 != null)
			last.next = list1;
		else if(list2 != null)
			last.next = list2;
		return head.next;
	}

}


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。