首页 > ACM题库 > LeetCode > LeetCode-Sort List[排序]
2014
11-19

LeetCode-Sort List[排序]

Sort List

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

标签: Linked List Sort
分析

常数空间且$O(nlogn)$,单链表适合用归并排序,双向链表适合用快速排序。本题可以复用 "Merge Two Sorted Lists" 的代码。

代码1

// LeetCode, Sort List
// 归并排序,时间复杂度O(nlogn),空间复杂度O(1)
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (head == NULL || head->next == NULL)return head;

        // 快慢指针找到中间节点
        ListNode *fast = head, *slow = head;
        while (fast->next != NULL && fast->next->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
        }
        // 断开
        fast = slow;
        slow = slow->next;
        fast->next = NULL;

        ListNode *l1 = sortList(head);  // 前半段排序
        ListNode *l2 = sortList(slow);  // 后半段排序
        return mergeTwoLists(l1, l2);
    }

    // Merge Two Sorted Lists
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(-1);
        for (ListNode* p = &dummy; l1 != nullptr || l2 != nullptr; p = p->next) {
            int val1 = l1 == nullptr ? INT_MAX : l1->val;
            int val2 = l2 == nullptr ? INT_MAX : l2->val;
            if (val1 <= val2) {
                p->next = l1;
                l1 = l1->next;
            } else {
                p->next = l2;
                l2 = l2->next;
            }
        }
        return dummy.next;
    }
};

Java代码:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    	public static  ListNode sortList(ListNode head) {
	    if(head == null || head.next == null) return head;
		ListNode slow = head;
		ListNode fast = head;
	    while(fast.next != null && fast.next.next != null){
	    	slow = slow.next;
	    	fast = fast.next.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 newHead = new ListNode(0);
		ListNode last = newHead;
		last = newHead;
		while(list1 != null && list2 != 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 newHead.next;
	}
}

相关题目
Insertion Sort List


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。