排序链表

来自Leetcode第148题排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

---

冒泡

将所有结点放入一个Hashset里，最后依次取出最小值，倒数第二个用例时超时

public ListNode sortList(ListNode head) {
    if(head == null || head.next == null)
        return head;
    Set<ListNode> list = new HashSet<ListNode>();
    ListNode p1 = head;
    while (p1 != null){
        list.add(p1);
        //System.out.print(p1);
        p1 = p1.next;
    }
    ListNode newHead = new ListNode(0);
    int k = 0;
    //Iterator<Map.Entry<ListNode,Integer>>  it = list.entrySet().iterator();
    while (!list.isEmpty()){
        Iterator<ListNode>  it = list.iterator();
        ListNode p2 = new ListNode(0);
        int val = Integer.MAX_VALUE;
        while (it.hasNext()){
            ListNode temp = it.next();
            if(temp.val < val){
                p2 = temp;
                val = temp.val;
            }
        }
        if(k == 0){
            newHead.val = p2.val;
            k++;
            p1 = newHead;
        }
        else{
            p1.next = p2;
            p1 = p1.next;
        }
        list.remove(p2);
    }
    p1.next = null;
    return newHead;
}

递归归并排序

来自题解

通过递归实现链表归并排序，有以下两个环节：

• 分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
  • 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
    • 找到中点 slow 后，执行 slow.next = None 将链表切断。
    • 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
  • cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。
• 合并 merge 环节： 将两个排序链表合并，转化为一个排序链表。
  • 双指针法合并，建立辅助ListNode h 作为头部。
  • 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
  • 返回辅助ListNode h 作为头部的下个节点 h.next。
  • 时间复杂度 O(l + r)，l, r 分别代表两个链表长度。
• 当题目输入的 head == None 时，直接返回None。

public ListNode sortList(ListNode head) {
    if(head == null || head.next == null)
        return head;
    ListNode fast = head.next,slow = head;
    //声明两个快慢指针
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode tmp = slow.next;
    //此时temp是中点后一个结点
    //若是偶数结点，tmp在中点偏右
    //奇数结点，tmp在中点后一个
    slow.next = null;
    //切割链表
    ListNode left = sortList(head);
    ListNode right = sortList(tmp);
    //递归分割左右链表
    ListNode h = new ListNode(0);
    //头结点作为合并链表的开始
    ListNode res = h;
    while (left != null && right != null){
        //合并过程
        if(left.val < right.val){
            h.next = left;
            left = left.next;
        }else {
            h.next = right;
            right = right.next;
        }
        h = h.next;
    }
    h.next = left != null ? left : right;
    return res.next;
}

链表转为数组排序后在转回链表

来自评论区，首先将链表转为数组，对数组做排序后在放回链表里。

public ListNode sortList(ListNode head) {
    if(head == null || head.next == null)
        return head;
    ListNode p1 = head;
    List<Integer> list = new ArrayList<>();
    while (p1 != null){
        list.add(p1.val);
        p1 = p1.next;
    }
    Collections.sort(list);
    Iterator<Integer> it = list.iterator();
    p1 = head;
    while (it.hasNext()){
        head.val = it.next();
        head = head.next;
    }
    return p1;
}