单链表的排序

import java.util.*;
public class Solution {
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode slow = dummyHead;
        ListNode fast = dummyHead;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode list2 = slow.next;
        slow.next = null;

        ListNode left = sortInList(dummyHead.next);
        ListNode right = sortInList(list2);

        return merge(left, right);

    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode p = dummyHead;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        p.next = list1 == null ? list2 : list1;

        return dummyHead.next;
    }
}

public ListNode sortInList (ListNode head) {
        return sort5(head);
    }

    public void print(ListNode head){
        while (head != null){
            System.out.print(head.val);
            System.out.print(",");
            head = head.next;
        }
        System.out.println();
    }
    public void print(ArrayList<ListNode> list){
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i).val);
            System.out.print(",");
        }
        System.out.println();
    }
    // 转数组，自排序
    public ListNode sort5(ListNode head){
        ArrayList<ListNode> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        Collections.sort(list,(s1,s2) -> s1.val-s2.val);
        ListNode const_node = new ListNode(999);
        ListNode pre = const_node;
        for(int i=0;i<list.size();i++){
            pre.next = list.get(i);
            pre = pre.next;
        }
        pre.next = null;
        return const_node.next;
    }
    //转数组
    public ListNode sort4(ListNode head){
        print(head);
        ArrayList<ListNode> list = new ArrayList<>();
        while(head != null){
            list.add(head);
            head = head.next;
        }
        print(list);
        sort4_1(list,0,list.size()-1);
        ListNode const_node = new ListNode(999);
        ListNode pre = const_node;
        for(int i=0;i<list.size();i++){
            pre.next = list.get(i);
            pre = pre.next;
        }
        pre.next = null;
        return const_node.next;
    }

    public void sort4_1(ArrayList<ListNode> list,int s,int e){
        if(s == e) return;
        int m = (s+e)/2;
        sort4_1(list,s,m);
        sort4_1(list,m+1,e);
        int m_tmp = m;
        ListNode node1,node2;
        while(s <= m_tmp && m+1 <= e){
            System.out.println(s);
            System.out.println(m);
            System.out.println(e);
            node1 = list.get(s);
            node2 = list.get(m+1);
            if(node1.val > node2.val){
                list.remove(m+1);
                list.add(s,node2);
                s++;
                m++;
                m_tmp++;
            }else{
                s++;
            }
            print(list);
        }
        System.out.println("===");
    }
    // 递归
    public ListNode sort3(ListNode head){
        if(head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode node2 = sort3(slow.next);
        slow.next = null;
        ListNode node1 = sort3(head);
        return sort3_merge(node1,node2);
    }
    public ListNode sort3_merge(ListNode node1,ListNode node2){
        ListNode const_node = new ListNode(99);
        ListNode pre = const_node;
        while(node1 != null && node2 != null){
            if(node1.val < node2.val){
                pre.next = node1;
                node1 = node1.next;
            }else{
                pre.next = node2;
                node2 = node2.next;
            }
            pre = pre.next;
        }
        if(node1 != null) pre.next = node1;
        if(node2 != null) pre.next = node2;
        return const_node.next;
    }
    // 插入排序
    public ListNode sort2 (ListNode head) {
        if(head == null) return head;
        ListNode const_node = new ListNode(999);
        const_node.next = head;
        ListNode node1 = head;
        while(node1!= null && node1.next != null){
            ListNode node2 = const_node;
            boolean is_insert = false;
            if(node1.next.val >= node1.val){
                node1 = node1.next;
                continue;
            }
            while(node2.next != node1.next){
                if(node1.next.val < node2.next.val){
                    ListNode tmp = node1.next;
                    node1.next = node1.next.next;
                    tmp.next = node2.next;
                    node2.next = tmp;
                    node1 = node1;
                    is_insert = true;
                    break;
                }
                node2 = node2.next;
            }
            System.out.println(node1.val);
            print(head);
            if(!is_insert) node1 = node1.next;
        }
        return const_node.next;
    }

    // 冒泡排序
    public ListNode sort1 (ListNode head) {
        if(head == null) return head;
        ListNode const_node = new ListNode(999);
        const_node.next = head;
        ListNode pre_node = const_node.next;
        ListNode next_node = pre_node.next;
        while(pre_node.next != null){
             if(next_node.val < pre_node.val){
                int tmp = next_node.val;
                next_node.val = pre_node.val;
                pre_node.val = tmp;
             }
             next_node = next_node.next;
             if(next_node == null){
                pre_node = pre_node.next;
                next_node = pre_node.next;
             }
        }
        return const_node.next;
    }

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here

        // 借助小根堆实现 - 注意别忘了自定义类的排序需要写比较器

        // 算法时间复杂度O(NlogN)，额外空间复杂度O(N)

        // 1.先排除null和单值
        if(head == null || head.next == null) {
            // 无需排序
            return head;
        }

        // 2.遍历链表，依次将结点入堆
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
        ListNode cur = head;
        while (cur != null) {
            // 堆的插入 - offer
            minHeap.offer(cur);
            System.out.println("结点入堆：" + cur.val);
            cur = cur.next;
        }

        // 3.依次出堆，尾插法建立result链表
        ListNode result = null;
        ListNode tail = result;
        while(!minHeap.isEmpty()) {
            // 依次弹出堆中所有结点，使用尾插法将它们连接起来
            // 堆的弹出 - poll
            ListNode rootNode = minHeap.poll();
            System.out.println("结点出堆：" + rootNode.val);
            rootNode.next = null;
            if (tail == null) {
                // 尾插第一个元素
                result = rootNode;
                tail = result;
            } else {
                tail.next = rootNode;
                tail = rootNode;
            }
        }
        // 4.返回结果链表的头结点result
        return result;
    }
}

    最小堆排序，时间复杂度为 nlogn
    public ListNode sortInList (ListNode head) {
        Queue<Integer> queue = new PriorityQueue<>();
        ListNode index = head;
        while(index != null){
            queue.add(index.val);
            index = index.next;
        }
        ListNode node = new ListNode(-1);
        index = node;
        while(!queue.isEmpty()){
            index.next = new ListNode(queue.poll());
            index = index.next;
        }
        return node.next;
    }

public ListNode sortInList (ListNode head) {
    // write code here
    PriorityQueue<ListNode> queue=new PriorityQueue<ListNode>(new Comparator<ListNode>(){
        @Override
        public int compare(ListNode l1 ,ListNode l2){
            return l2.val-l1.val;
        }
    });;
    while(head!=null){
        queue.add(head);
        head=head.next;
    }
    ListNode pre=new ListNode(0);
    while(!queue.isEmpty()){
        ListNode node=queue.poll();
        node.next=pre.next;
        pre.next=node;
    }
    return pre.next;
}

public ListNode sortInList (ListNode head) {
    // write code here
    ArrayList<Integer> nums = new ArrayList<Integer>();
    nums.add(head.val);
    while(head.next != null){
        head = head.next;
        nums.add(head.val);
    }
    Collections.sort(nums);
    ListNode newHead = new ListNode(-1);
    ListNode temp = newHead;
    for(int i=0; i< nums.size(); i++){
        ListNode num = new ListNode(nums.get(i));
        temp.next = num;
        temp = temp.next;
    }

    return newHead.next;
}

import java.util.*;



/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if(head==null) return null;
        ListNode p = head;
        List<Integer> list = new ArrayList<>();
        while(p!=null){
            list.add(p.val);
            p=p.next;
        }
        p=head;
        Collections.sort(list);
        int[] arr= list.stream().mapToInt(Integer::valueOf).toArray();
        for(int i=0;i<list.size();i++){
            p.val=arr[i];
            p=p.next;
        }
        return head;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    int count = 0;
    public ListNode sortInList (ListNode head) {
        // write code here
        return diviveAndMerge(head);
    }

    public ListNode diviveAndMerge(ListNode head) {
        // 链表为空或只有一个元素时返回
        if (head == null || head.next == null) return head;
        // 中点的前序节点，即左侧节点
        ListNode left = head;
        // 中心节点
        ListNode mid = head.next;
        // 右侧节点
        ListNode rigth = head.next.next;
        while (rigth != null && rigth.next != null) {
            left = left.next;
            mid = mid.next;
            // 右侧节点速度是左侧节点的2倍
            rigth = rigth.next.next;
        }
        // 将链表从left与mid之间断开，切分成head和mid两部分
        left.next = null;
        // 递的过程不断将集合化为两半
        ListNode node1 = diviveAndMerge(head);
        ListNode node2 = diviveAndMerge(mid);
        // 归的过程将两个链表合并，返回值为合并后的头节点
        return mergeTwoListNode(node1, node2);
    }

    // 合并两个链表
    public ListNode mergeTwoListNode(ListNode pHead1, ListNode pHead2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (pHead1 != null && pHead2 != null) {
            if (pHead1.val <= pHead2.val) {
                cur.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;
        }
        cur.next = pHead1 != null ? pHead1 : pHead2;
        return dummy.next;
    }

家人们谁懂啊，用快排的思想可以做吗？
22/23测试用例。

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);
        ListNode target = head, p = head.next;
        ListNode p1 = dummy1, p2 = dummy2;
        while (p != null) {
            if (p.val < target.val) {
                p1.next = p;
                p1 = p1.next;
                p = p.next;
                p1.next = null;
            } else {
                p2.next = p;
                p2 = p2.next;
                p = p.next;
                p2.next = null;
            }
        }
        p1.next = target;
        p1 = p1.next;
        p1.next = null;
        ListNode leftParted = sortInList(dummy1.next);
        ListNode rightParted = sortInList(dummy2.next);
        ListNode temp = leftParted;
        while (temp.next != null) temp = temp.next;
        temp.next = target;
        target.next = rightParted;
        return leftParted;
    }
}

public ListNode sortInList(ListNode head) {
        //把一个链表从中间拆成两个链表
        if(head==null||head.next==null) return head;
        ListNode fast=head;
        ListNode slow=head;
        ListNode slowPre=null;//注意这里是null，而不是new ListNode(0)
        //找链表中点
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            slowPre=slow;//第一次的时候就已经是head.next，slow直接跳跃了head
        }
        //根据fast，确定中点   ***z注意这个左右中点的区分
        ListNode nextHead;
        nextHead=slow.next;
        slow.next=null;
        //合并两个有序链表
        //各自排序
        ListNode node1=sortInList(head);
        ListNode node2=sortInList(nextHead);
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        //合并
        while(node1!=null&&node2!=null){
            if(node1.val<node2.val){
                cur.next=node1;
                node1=node1.next;
                cur=cur.next;
            }else{
                cur.next=node2;
                node2=node2.next;
                cur=cur.next;
            }
        }
        while(node1!=null){
            cur.next=node1;
            node1=node1.next;
            cur=cur.next;
        }
        while(node2!=null){
            cur.next=node2;
            node2=node2.next;
            cur=cur.next;
        }
        return dummy.next;

    }

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (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;
        slow.next = null;

        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);

        ListNode dummyHead = new ListNode(-1);
        ListNode curr = dummyHead;

        while (left != null && right != null) {
            if (left.val < right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }

            curr = curr.next;
        }

        curr.next = left != null ? left : right;
        return dummyHead.next;
    }
}