leetCode解题报告之Sort List

你的名字 2022-08-25 15:55 91阅读 0赞

**勉励自己：坚持，谁说做工程的人不能学好算法！为面试做准备,加油！！！！！**

**题目：**

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

**分析：**

**题目要求我们要用一个复杂度O(nlogn)的排序算法来排序一个链表，复杂度O(nlogn)的排序算法包括：[快速排序][Link 1]，[堆排序，希尔排序，二叉排序树排序][Link 2]，[归并排序][Link 3]**

**情况：**

**考虑到题目的要求，我个人觉得用“归并排序”会比较好！**

**第一次提交没AC的[Time Limit Exceeded][]代码：(没有考虑到两个递归之后的子链表做排序的话，关于合并的时间消耗)**

package cn.xym.leetcode.sortlist;
    
    
    public class Solution1 {
    	
    	public ListNode sortList(ListNode head) {
    		if (head == null || head.next == null)
    			return head;
    		int len = getListSize(head);
    		mergerSort(head, 0, len-1);
    		
    		return head;
    	}
    	public void mergerSort(ListNode head, int left, int right){
    		int mid = (right+left) / 2;
    		if (left == right)
    			return;
    		else{
    			int first = left;
    			int last = right;
    			mergerSort(head, first, mid);
    			mergerSort(head, mid+1, last);
    			mergerListNode(head, first, mid, last);
    		}
    	}
       public void mergerListNode(ListNode head, int left,int mid,int right){
    		int left1 = 0;
    		int right1 = mid - left;
    		int left2 = 0;
    		int right2 = right - mid - 1;
    		int k = 0;
    		
    		ListNode node1 = getListNode(head, left);
    		ListNode node2 = getListNode(head, mid+1);
    		int[] temp = new int[right - left + 1];
    		
    		while (left1 <= right1 && left2 <= right2){
    			ListNode temp1 = getListNode(node1, left1);
    			ListNode temp2 = getListNode(node2, left2);
    			if (temp1.val < temp2.val){
    				temp[k++] = temp1.val;
    				left1++;
    			}else{
    				temp[k++] = temp2.val;
    				left2++;
    			}
    		}
    		while (left1 <= right1){
    			temp[k++] = getListNode(node1, left1).val;
    			left1++;
    		}
    		while (left2 <= right2){
    			temp[k++] = getListNode(node2, left2).val;
    			left2++;
    		}
    		for (int i=0; i<k; ++i){
    			getListNode(head, i + left).val = temp[i];
    		}
    	}
    	
    	public ListNode getListNode(ListNode head, int index){
    		ListNode temp = head;
    		for (int i=0; i<index; ++i){
    			temp = temp.next;
    		}
    		return temp;
    	}
    	public int getListSize(ListNode head){
    		int len = 0;
    		while (head != null){
    			len++;
    			head = head.next;
    		}
    		return len;
    	}
    	
    	public static void main(String[] args) {
    		ListNode head1 = new ListNode(10);
    		ListNode head2 = new ListNode(40);
    		ListNode head3 = new ListNode(6);
    		ListNode head4 = new ListNode(22);
    		ListNode head5 = new ListNode(1);
    		ListNode head6 = new ListNode(30);
    		head1.next = head2;
    		head2.next = head3;
    		head3.next = head4;
    		head4.next = head5;
    		head5.next = head6;
    		head6.next = null;
    		Solution1 solution = new Solution1();
    		solution.sortList(head1);
    		while (head1 != null){
    			System.out.println(head1.val);
    			head1 = head1.next;
    		}
    	}
    }

下面是AC的代码：

package cn.xym.leetcode.sortlist;
    
    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;
    		int len = getSize(head);
    		ListNode list = mergerSort(head,len);
    		return list;
    	}
    
    	public ListNode mergerSort(ListNode head, int len) {
    		
    		if (len == 1)
    			return head;
    		//找出当前head链表中间的ListNode
    		int middle = len / 2;
    		ListNode preMiddleNode = getListNode(head, middle-1);
    		ListNode endNode = getListNode(head, len-1);
    		ListNode middleNode = preMiddleNode.next;
    		preMiddleNode.next = null;
    		endNode.next = null;
    		
    		int leftLen = getSize(head);
    		int rightLen = getSize(middleNode);
    		
    		ListNode leftList = mergerSort(head, leftLen);
    		ListNode rightList = mergerSort(middleNode, rightLen);
    		ListNode allList = mergerListNode(leftList, rightList);
    		return allList;
    	}
    	/*返回一个局部排序好的表*/
    	public ListNode mergerListNode(ListNode left, ListNode right) {
    		ListNode temp = new ListNode(Integer.MIN_VALUE);
    		ListNode preHead = new ListNode(Integer.MIN_VALUE);
    		preHead = temp;
    		
    		//两个排序好的链表进行合并
    		while (left != null && right != null){
    			if (left.val < right.val){
    				temp.next = left;
    				left = left.next;
    			}else{
    				temp.next = right;
    				right = right.next;
    			}
    			temp = temp.next;
    		}
    		if (left == null){
    			temp.next = right;
    		}
    		if (right == null){
    			temp.next = left;
    		}
    		
    		return preHead.next;
    	}
    
    	public ListNode getListNode(ListNode head, int index) {
    		ListNode temp = head;
    		for (int i = 0; i < index; ++i) {
    			temp = temp.next;
    		}
    		return temp;
    	}
    
    	public int getSize(ListNode head) {
    		int len = 0;
    		while (head != null) {
    			len++;
    			head = head.next;
    		}
    		return len;
    	}
    
    	public static void main(String[] args) {
    		ListNode head1 = new ListNode(10);
    		ListNode head2 = new ListNode(40);
    		ListNode head3 = new ListNode(6);
    		ListNode head4 = new ListNode(22);
    		ListNode head5 = new ListNode(1);
    		ListNode head6 = new ListNode(30);
    		head1.next = head2;
    		head2.next = head3;
    		head3.next = head4;
    		head4.next = head5;
    		head5.next = head6;
    		head6.next = null;
    		Solution solution = new Solution();
    		head1 = solution.sortList(head1);
    		while (head1 != null) {
    			System.out.println(head1.val);
    			head1 = head1.next;
    		}
    	}
    }

[Link 1]: http://baike.baidu.com/view/19016.htm?fromtitle=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&fromid=2084344&type=syn
[Link 2]: http://baike.baidu.com/view/647462.htm
[Link 3]: http://baike.baidu.com/view/90797.htm
[Time Limit Exceeded]: http://oj.leetcode.com/submissions/detail/4625995/