链表的排序算法

48. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：

输入：head = []
输出：[]

    static ListNode merge(ListNode l1, ListNode l2){
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(l1 != null &&  l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur =cur.next;
        }
        if(l1!= null){
            cur.next = l1;
        }
        if(l2 != null){
            cur.next = l2;
        }
        return head.next;
    }
    static ListNode sortList02(ListNode head, ListNode tail){
        if(head == null){
            return head;
        }
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null &&  fast != tail){
            fast = fast.next;
            slow = slow.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode l1 = sortList02(head, mid);
        ListNode l2 = sortList02(mid, tail);
        ListNode sorted = merge(l1,l2);
        return sorted;
    }
    static ListNode sort(ListNode head){
        ListNode res = sortList02(head, null);
        return res;
    }
   
   

       寻找链表的中点

         ListNode fast = head;
        ListNode slow = head;
        while(fast != null &&  fast != tail){
            fast = fast.next;
            slow = slow.next;
            if(fast != tail){
                fast = fast.next;
            }
        } 

链表插入排序

 static ListNode sortList(ListNode head) {
        ListNode cur = head;
        ListNode newHead = new ListNode(-1);
        while (cur != null) {
            ListNode nextNode = cur.next;
            if (newHead.next == null) {
                newHead.next = cur;
                cur.next = null;
            } else {
                ListNode p = newHead.next;
                ListNode pre = newHead;
                while (p != null && p.val < cur.val) {
                    pre = p;
                    p = p.next;
                }
                if (p != null) {
                    cur.next = p;
                    pre.next = cur;
                }else{
                    pre.next = cur;
                    cur.next = null;
                }
            }
            cur = nextNode;
        }
        return newHead.next;
    }

 138. 随机链表的复制

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }
        if(!cached.containsKey(head)){
            Node node = new Node(head.val);
            cached.put(head,node);
            node.next = copyRandomList(head.next);
            node.random = copyRandomList(head.random);
        }
        return cached.get(head);
    }

这道题挺唬人的，但是只要记住管他随机链表，只要复制节点数据就行