链表练习-力扣题解

第一节介绍了常用的三种链表：单链表、双向链表、环形链表，一节各自的增删遍历方式，作为基础的回顾。
第二节12道力扣经典的链表题练手，链表题没有统一的套路、但有许多必须掌握的常识：链表拼接、哑巴结点、快慢指针、反转链表、寻找中间结点等。反正就是多练。
第三节是简单的总结，没什么卵用。

[1]原理部分参考了码农StayUp的文章https://segmentfault.com/a/1190000038252047

[3]啊我写到一半看到力扣上一个超牛批的题解文章，再看我总结的,,,,这不就是shi么，,贴个链接以后可以回看：作者Time-Limit链接：https://leetcode-cn.com/problems/linked-list-cycle/solution/yi-wen-gao-ding-chang-jian-de-lian-biao-wen-ti-h-2/

除文中标注处以外，文字、代码都是自我理解写的，不对之处敬请指出，保留权利。

1 链表结构介绍

此节图片来源于[1]，谢谢谢谢谢（我就是懒）

当我再一次打开链表的简单题，发现我连链表的遍历都忘了的时候我就知道，“脑子是不顶用的，但键盘可以”。所以只是做做笔记、方便闲的dan疼的时候回看。

链表是以节点（Node）的方式来存储，其节点的逻辑顺序与物理顺序(内存)可以不一致[1]
相比数组，链表的增删快而查找慢。当数据结构的大小容量未知、查找少的场合推荐使用链表储存
链表分为单链表、双链表和环形链表。双链表改善单链表的查询时间复杂度，环形链表改善空间复杂度

1.1 单链表

单链表的遍历：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

//单链表的遍历 宇宙常识
ListNode cur = head;
while(cur!=null){
    System.out.printlin(cur.val);
    cur = cur.next;
}

单链表的插入操作:

插入操作伪代码，先处理2 再处理1、、或者都行？

//插入操作伪代码 先处理2再处理1
ListNode nodeNew = ListNode('X'); //新增节点
ListNode cur = head;
while(cur!=null){
    if(cur.val=='A1'){
        nodeNew.next = cur.next;
        cur.next = nodeNew;
        break;
    }
    //System.out.printlin(cur.val);
    cur = cur.next;
}

单链表的删除操作:

删除操作一般处理当前节点的下一个节点，所以遍历循环条件为cur.next!=null

ListNode cur = head;
while(cur.next!=null){
    if(cur.next.val=='A1'){
        cur.next = cur.next.next;
        break;
    }
    //System.out.printlin(cur.val);
    cur = cur.next;
}

技巧一：运用哑巴节点

链表的头节点也可能被删除，这里要用哑巴节点dummy node辅助删除

//借用哑巴节点处理头节点的情况
ListNode dummyNode= new ListNode(0);
dummyNode.next = head;
head = dummyNode;//重复使用head作为cur
while(head.next!=null){
    //根据条件操作链表元素
    ...
    //后移遍历
    head = head.next;
}
return dummyNode.next;

技巧二：反转链表

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //指定一个反转的结果 和一个当前链表
        ListNode prev=null;
        ListNode cur=head;
        while(cur!=null){
            //保存下一个链表 方便遍历
            ListNode tempNode = cur.next;
            
            //将当前节点指向反转链表
            cur.next = prev;
            //移动反转链表的头
            prev = cur;
            
            //向下一个节点移动、遍历
            cur = tempNode;
        }
        return prev;
    }
}

1.2 双向链表

双向链表就是双车道了两头都可以跑，如果知道某一个节点的索引与数组最大索引/2的大小关系，就可以判断应该正向遍历或者反向遍历查找，这其实是一种以空间换取时间的策略，将原先查找O(n)的时间复杂度变为O(n/2)，应该还是能快一些。（我一月份背的八股居然还没忘/狗头）

双向链表的首尾节点和中间节点是不一样的，具体怎么定义、我还没看…这里只考虑对中间节点的操作

双向链表的遍历

两个方向都可以，还是只写一个方向的 (我瞎写的也不知道对不对，反正考的少)

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
};
*/
Node cur = first;
while(cur!=null){
    System.out.println(cur.val);
    cur = cur.next; //从头节点开始正向遍历
    if(cur.next.equals(cur.prev) ) break; //表示到了尾节点
}

双向链表的插入

向双链表中插入一个新节点，需要通过调整两次prev指向和两次next指向来完成[1]。一定要注意顺序、参考文献[1]这里有些误人子弟了，口诀是 **”0点开始顺时针”**（我他娘真是个天才）

Node nodeNew = new Node('X');
Node cur = first;
while(cur!=null){
    if(cur.val=='A1'){
        nodeNew.next = cur.next;
        cur.next.prev = nodeNew;
        nodeNew.prev = cur;
        cur.next = nodeNew;
    }
    //System.out.println(cur.val);
    cur = cur.next;
    if(cur.next.equals(cur.prev) ) break;
}

双向链表的删除

删除节点分为两步，“三点开始顺时针”
删除操作一般处理当前节点的下一个节点，所以遍历循环条件为cur.next!=null

//双向链表删除节点 这里还只能处理非首尾节点
Node cur = first;
while(cur.next!=null){
    if(cur.next.val=='A2'){
        cur.next.next.prev = cur;
        cur.next = cur.next.next;
        nodeNew.prev = cur;
        cur.next = nodeNew;
    }
    //System.out.println(cur.val);
    cur = cur.next;
    if(cur.next.equals(cur.prev) ) break;
}

1.3 单向环形链表

与单链表的唯一区别是尾部节点的next不再为空，则是指向了头部节点，这样便形成了一个环。[1]

环形链表的遍历

环形链表主类里面必然有两个特殊的首尾指针节点first 和 last,实现起来挺困难，特别是插入删除均要考虑相对的位置，这里只列遍历吧：

//环形链表的遍历
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *	  //节点的构造方法：初始化数据域，将节点指向空
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
ListNode cur = first;
while(cut!=last){
    System.out.println(cur.val);
    cur = cur.next;
}
System.out.println(cur.val); //打印尾节点的值

2 力扣题解_链表

开始搞题，理论部分搞不动了。2.1-2.4先把快慢指针或者说双指针搞爽。

2.1 剑指offer22.链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

思路：前后两个指针left、right它们相距k的长度，同步的移动，当right到达链表尾部时，left到达倒数第k个节点处。（图片源于[3]）

代码：画一下就能知道两指针的索引相减等于k-1，所以第一步right只需移动k-1格就好了

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode right = head;
        ListNode left = head;
        for(int i=1;i<k;i++){
            right = right.next;
        }

        while(right.next!=null){
            right = right.next;
            left = left.next;
        }
        return left;
    }
}

2.2 力扣867.链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

思路：快慢指针，快指针步长为2，慢指针步长为1，当快指针指向链表末尾时，慢指针指向中间节点。特别的当结点个数为奇数时，慢指针指向中间结点；当偶数时，慢指针指向中间两个结点中靠前或者靠后的一个（用一个6结点的链表画一下图就清楚了）下图来源于[3]

当fast=head slow=head时，偶数情况将返回第二个中间结点
当fast=head.next slow=head，偶数情况将返回第一个中间结点

代码一：返回第二个中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow; //偶数时返回第二个中间结点
    }
}

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //为偶数时fast不为空，返回slow的下一个
        if(fast!=null) return slow.next;
        //奇数时 直接返回即可
        return slow;
    }
}

代码二：返回第一个中间结点

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //此时偶数时slow是第一个中间节点
        return slow; 
    }
}

2.3 力扣环形链表

来两道环形链表的力扣题体验一下，实际上也是双指针快慢指针的题。

141环形链表Ⅰ

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：
1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

思路：

1、判断是否成环，可以用hashset集合存每个节点，如果遍历过程发现该节点已经存在于集合中就表示成环了
2、链表题目想要常数的空间复杂度、好像就是双指针莽起来。双指针是一种思想：有快慢指针、首尾指针、等间隔指针等。

代码实现：快慢指针

对于成环链表，进入链表环内的两个快慢指针终会相遇。（就像是跑操场，跑得快的人必然会追上跑得慢的人）
其实效率有一点需要考量：
- 因为快指针有些节点永远都不能到达、当第一圈两指针接近但没有重合，就只能再多跑一圈才能真正相遇。
- 慢指针步长设为1，快指针步长设为2；虽然如果快指针步长设更大时会追赶的更快，但是会出现更多不能到达的节点，有可能得不偿失
- 快指针步长为2 注意while循环的判断条件是fast&fast.next都不为空

public class Solution {
    public boolean hasCycle(ListNode head) {
        //快慢指针  注意while循环的判断条件是fast&fast.next都不为空
        if(head==null) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            if(fast==slow) return true;
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }
}

代码实现：set集合

public class Solution {
    public boolean hasCycle(ListNode head) {
        //使用set集合存路径走过的节点
        Set<ListNode> visited = new HashSet<>();
        ListNode cur = head;
        while(cur!=null){
            if(visited.contains(cur)) return true;
            visited.add(cur);
            cur = cur.next;
        }
        return false;

    }
}

142环形链表Ⅱ

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。你是否可以使用 O(1) 空间解决此题？

示例 1：
1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

思路一：用set集合存节点，找到第一个重复出现的节点就返回

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //方法一 hashset存节点 第一个重复出现的节点 返回即可
        Set<ListNode> visited = new HashSet<>();
        ListNode cur = head;
        while(cur!=null){
            if(visited.contains(cur)) return cur;
            visited.add(cur);
            cur = cur.next;
        }
        return null;
    }
}

思路二：快慢指针 [图片来源于力扣官方题解]

解释一下，慢指针走过a+b，快指针走过a+b+k(b+c)，且快指针走过的距离是慢指针的两倍，所以有a+b=k(b+c)，可以得到a=(k-1)(b+c)+c。也就是说如果知道相遇点了（如图紫色的位置）。放指针1从头开始走、指针2从相遇点开始走，指针1走过a步,指针2走过k-1圈+c步后，两指针会相遇在链表环路的起点。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //方法二 快慢指针公式推导
        if(head==null) return null;
        ListNode fast = head.next;
        ListNode slow = head;
        while(fast!=null && fast.next!=null){
            if(fast == slow) break; //找到相遇节点就跳出
            fast = fast.next.next;
            slow = slow.next;
        }
        //快指针作为指针1从头开始跑 慢指针作为指针2接着跑
        fast = head;  //指针1
        slow = slow.next;  //指针2
        while(fast.next!=null && slow.next!=null){
            if(fast == slow) return fast;
            fast = fast.next;
            slow = slow.next;
        }
        return null;
    }
}

2.4 剑指Offer52. 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

思路

两个链表长度分别为L1+C、L2+C， C为公共部分的长度
cur1 cur2都走了 L1+L2 +C +1步之后相遇（1是null的位置）
要多走一步null 以便不相交时也能跳出循环（当cur1 cur2都走过了L1+L2的长度时都为null,此时跳出循环）

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        while(cur1!=cur2){
            if(cur1==null) cur1 = headB; else cur1 = cur1.next;
            if(cur2==null) cur2 = headA; else cur2 = cur2.next;
        }
        return cur1;
    }
}

2.5 力扣83/82.删除排序链表中的重复元素

删除排序链表中的重复元素Ⅰ

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

头节点不用动，删除节点只需要移动指针，注意连续相同的元素用while判断一次性全部删除。

这题判断条件容易出错，因为可能有多个重复元素，内部需要循环判断是否重复
只要某循环里面要用到cur.next，就一定要在循环判断条件里面加上cur.next!=null

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        //头节点不用动，删除节点只需要移动指针
        ListNode temp = head;
        while(temp!=null){
            while(temp.next!=null && temp.val==temp.next.val)
                temp.next = temp.next.next;
            temp = temp.next;
        }
        return head;
    }
}

删除排序链表中的重复元素Ⅱ

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

**头节点可能会动掉，搞个哑巴节点dummyNode**。这题也很容易出错啊、我做第三遍又没调试好。。

要想删完重复的（如a b b b c）、先判断是不是有重复、有重复就内部while循环，cur要指向a，记录b的值每次删一个b。
还有head节点如果没用了、可以直接拿来做指针

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        //头节点可能会动掉，搞个哑巴节点
        ListNode dummyNode =new ListNode(0);
        dummyNode.next = head;
        head = dummyNode;
        while(head.next!=null&&head.next.next!=null){
            //先判断有没有出现相等，有就while删完全，没有就下一个
            if(head.next.val==head.next.next.val){
                int tempVal = head.next.val;
                while(head.next!=null&&head.next.val==tempVal) 
                    head.next=head.next.next;
            }else{
                head = head.next;
        }
        return dummyNode.next;
    }
}

2.6 力扣92.反转链表Ⅱ(中等)

思路

反转链表的升级版，区别就是链表分为三段，只有第二段需要翻转，翻转完之后将三段链表再次连接起来。
想要连接起来必须有第一段的尾temp1 , 第二段的头prev，第二段的尾temp2，第三段的头cur
因为头节点有可能动所以用哑巴节点 dummyNode

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //先用自己朴素的思想来搞搞看
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head; // head指针没用了 所以用head作为当前节点
        head = dummyNode;
        int count = 0; //计数，表示当前节点是第几个节点，从1开始
        while(count<left-1){
            head = head.next;
            count++;
        } 
        ListNode temp1 = head; //记录第一段的尾巴 在循环外操作
        head = head.next;count++;

        ListNode temp2 = head; //记录第二段的尾巴
        //这时count==left 且 head指向了left处的元素,开始反转了要
        ListNode prev = null;
        while(count<=right){
            ListNode tempNode = head.next;
            head.next = prev;
            //调整prev 和 head
            prev = head;
            head = tempNode;
            count++;
        }
        //此时count = right+1 ,head指向第三段的头节点
        temp1.next = prev;
        temp2.next = head;
        return dummyNode.next;
    }
}

2.7 力扣21.合并两个有序链表(简单)

思路：

两个链表两个当前节点指针，哪个小就先加哪个喽

头节点不确定所以哑巴节点
可以直接使用两个子链表的头节点l1 l2作为指针

代码：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode temp = dummyNode;
        while(l1!=null && l2!=null){
            if(l1.val<=l2.val){
                temp.next = l1;
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
            temp = temp.next;
        }
        //连接上剩下不为空的链表
        if(l1==null) temp.next=l2; else temp.next=l1;
        return dummyNode.next;
    }
}

2.8 力扣86分隔链表（中等）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

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

思路一：大佬题解

将大于等于x值得节点取出放到另一个链表，然后连接两个链表。

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode headDummy = new ListNode(0);
        ListNode tailDummy = new ListNode(0);
        ListNode tail = tailDummy;
        headDummy.next = head;
        head = headDummy;
        while(head.next!=null){
            if(head.next.val>=x){
                // 1 原链表删除 
                ListNode nodeOut = head.next;
                head.next=head.next.next;
                // 2 新链表加入
                tail.next = nodeOut;
                tail=tail.next;
            }else{
                head=head.next;
            }
            
        }
        tail.next=null;
        head.next=tailDummy.next;
        return headDummy.next;

    }
}

思路二：我的思路

开始以为不能做，没想到也可以跑通，是比较质朴的思路。

指针定位，节点的删除和插入操作
一个指针flag定位第一个大于等于x的节点（小于的元素都要插到flag前）
一个指针location定位flag前最后一个节点，新元素插到其后，每一次插入后移一格
flag和location用来定位再用一个指针head用来遍历即可

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        head = dummyNode;
        ListNode flag = dummyNode;
        ListNode location = dummyNode;
        //找到flag的位置
        while(head.next!=null){
            if(head.next.val>=x){
                flag = head.next;
                location = head;
                break;
            }
            head = head.next;
        }
        // 多加一层判断，如果没有大于x的元素 直接返回原链表
        if(flag==dummyNode) return dummyNode.next;

        //从flag开始遍历，遇到大于x的元素 就先删除再插入
        head = flag;
        while(head.next!=null){
            if(head.next.val<x){
                //1保存 2删除 3插入
                ListNode temp = head.next;
                //删除
                head.next = head.next.next;
                //插入
                temp.next = flag;
                location.next = temp;
                location = location.next;
            }else{
                head = head.next;
            }
        }
        return dummyNode.next;
    }
}

2.9 力扣143.重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

一道比较综合的题，用到了查找中间节点、翻转链表、链表的插入操作

思路：

先找中间结点阶段，中间结点之后（不包括）的为链表2
链表2翻转得到链表3，
然后遍历链表3 直到它为null，，每次都做插入操作，插入之后注意链表1的指针移动

代码

class Solution {
    public void reorderList(ListNode head) {
        //1 这里先找第一个中间节点 分割出两链表
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //此时slow是第一个中间结点
        ListNode head2 = slow.next; //链表2的头节点
        slow.next = null; //链表1截断

        //2 翻转链表2成为 链表3
        ListNode head3 = null; //链表3的头节点
        while(head2!=null){
            ListNode tmepNode = head2.next;
            head2.next = head3;
            //重置head3 和 head2
            head3 = head2;
            head2 = tmepNode;
        }
        
        //3 将链表1和链表3插入拼接
        slow = head;
        while(head3!=null){
            //取节点 后移 插入
            ListNode temp = head3;
            head3 = head3.next;
            temp.next = slow.next;
            slow.next = temp;
            slow = slow.next.next;
        }
    }
}

2.10 力扣234.回文链表

请判断一个链表是否为回文链表。

示例 1:
1
2
输入: 1->2
输出: false
示例 2:
1
2
输入: 1->2->2->1
输出: true

重排链表会做了这题就简单了

思路：

1找中间节点，分隔成链表1 链表2
2翻转链表2
3遍历比较每个元素值是否相同

代码：

不要被示例误导，回文串也有奇数个元素的。head2和head1的长度可能不一样

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head==null) return true;
        //找中间节点 断开两链表
        ListNode fast = head.next; //此处找到第一个中间节点
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        } 
        ListNode head2 = slow.next;//slow是第一个中间节点
        slow.next = null; //断开链表1

        //翻转链表2
        head2 = reverseNode(head2);

        //遍历比较链表1 2
        while(head!=null&&head2!=null){
            //System.out.println(head.val+","+head2.val);
            if(head.val!=head2.val) return false;
            head = head.next;
            head2 = head2.next;
        }
        return true;

    }
    //翻转链表的函数
    public ListNode reverseNode(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode prev = null;
        ListNode cur = head;
        while(cur!=null){
            ListNode tempNode = cur.next;
            cur.next = prev;
            //调整prev cur
            prev = cur;
            cur = tempNode;
        }
        return prev;
    }
}

2.11 力扣138. 复制带随机指针的链表

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的深拷贝。深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random –> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random –> y 。

返回复制链表的头节点。

思路一：map集合赋值新旧节点

hashmap储存复制的节点，键为旧节点值为新节点
第一次遍历将每个节点的值复制进map中（此时next random指针都为空）
第二次遍历将每个节点的两个指针赋值给新节点
新节点要指向新节点所以要用map.get()

代码

class Solution {
    public Node copyRandomList(Node head) {
        //方法一 hashmap储存复制的节点，键为旧节点 值为新节点
        if(head==null) return null;
        Map<Node,Node> map =new HashMap<>();
        //第一次遍历将每个节点的值复制进map中 （此时next random指针都为空）
        Node cur = head;
        while(cur!=null){
            Node newNode = new Node(cur.val);
            map.put(cur,newNode);
            cur = cur.next;
        }
        //第二次遍历将每个节点的两个指针赋值给新节点
        cur = head;
        while(cur!=null){
            Node newNode = map.get(cur);
            //新节点要指向新节点所以要用map.get()
            if(cur.next!=null) newNode.next = map.get(cur.next); 
            if(cur.random!=null) newNode.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

思路二链表原地复制

1在每个节点后原地创建复制节点，此时节点中只有value
2用来设置新结点的随机指针, 即新节点的random指向对应旧结点随机指针的下一个
3只要将两个链表分离，返回新链表。集体操作就是一个新链表尾部添加、一个旧链表删除

代码：

class Solution {
    public Node copyRandomList(Node head) {
        //方法二 链表原地复制
        //1在每个节点后原地创建复制节点
        Node cur = head;
        while(cur!=null){
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next=newNode;
            cur = cur.next.next;
        }
        //2为每个新节点设置随机指针 即指向旧结点随机指针的下一个
        cur = head;
        while(cur!=null && cur.next!=null){
            if(cur.random!=null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        //3分离成新旧两个链表
        Node dummyNode = new Node(-1);
        Node cur2 = dummyNode;
        cur = head;
        while(cur!=null&&cur.next!=null){
            //新链表新增
            cur2.next = cur.next;
            cur2 = cur2.next;
            //旧链表删除
            cur.next = cur.next.next;
            cur = cur.next;
        }
        cur2.next = null;
        return dummyNode.next;
    }
}

2.12 力扣148.排序链表（中等）

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

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

示例 1：
1
2
>输入：head = [4,2,1,3]
>输出：[1,2,3,4]

思路：

归并排序的思想：“假设初始序列含有n 个记录，则可以看成是n 个有序（内部有序）的子序列，每个子序列的长度为 1 , 然后两两归并，得到[n /2] ([x ]表示不小于x 的最小整数）个长度为2 或 1 的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n 的有序序列为止。“

需要两个函数：一个函数MergeSort用来递归，将原链表平分为两个部分、分别递归调用生成有序链表；一个函数Merge合并两个有序子链表，主要采用两个指针轮流后移的方法。

递归的出口是子链表的长度为1
1先将一个长链表分为两个等长（或差1）的子链表
2分别对两个子链表进行归并排序
3合并两个已经有序的子链表

代码

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }

    private ListNode mergeSort(ListNode head){
        //递归出口 链表长度为1
        if(head==null|| head.next==null) return head;

        //找链表的中间结点（第一个中间结点） 分隔为两个链表
        ListNode midNode = findMid(head);
        ListNode head2 = midNode.next;//链表2
        midNode.next = null; //链表1截断

        //分别对两个子链表递归调用排序
        head = mergeSort(head);
        head2 = mergeSort(head2);

        //合并两个已经排好序的链表
        ListNode res = merge(head,head2);
        return res;
    }

    private ListNode findMid(ListNode head){
        ListNode fast = head.next;//找到第一个中间结点
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    private ListNode merge(ListNode head1, ListNode head2){
        //不确定头节点 借用dummyNode
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;
        while(head1!=null && head2!=null){
            if(head1.val<=head2.val){
                //加入结点
                cur.next = head1;
                cur = cur.next;
                head1 = head1.next;
            }else{
                cur.next = head2;
                cur = cur.next;
                head2 = head2.next;
            }
        }
        //拼接上剩下不为空的哪个链表
        if(head1==null) cur.next=head2; else cur.next = head1;
        return dummyNode.next; 
    }
}

为什么题解直接用归并，而不是用快排、堆排序？翻了一下还真有用快排和堆排序的题解，直接贴出来、以后再看。

链表的快排

class Solution {
    public static ListNode sortList(ListNode head) {
        return quickSort(head ,null);
    }

    public static ListNode quickSort(ListNode head ,ListNode end){
        if(head ==end || head.next ==end) return head;
        ListNode lhead = head ,utail = head ,p = head.next;
        while (p != end){
            ListNode next = p.next;
            if(p.val < head.val){//头插
                p.next = lhead;
                lhead = p;
            }
            else { //尾插
                utail.next = p;
                utail = p;
            }
            p = next;
        }
        utail.next = end;
        ListNode node = quickSort(lhead, head);
        head.next =  quickSort(head.next, end);
        return node;
    }
}

/*作者：yxj33
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-kuai-pai-fang-shi-by-yx-ahnt/
来源：力扣（LeetCode）
*/

链表的堆排（利用优先队列）

class Solution {

    public ListNode sortList(ListNode head) {

        if (head == null) return null;

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        ListNode p = head;
        while (p != null) {

            pq.offer(p.val);
            p = p.next;
        }

        ListNode q = new ListNode(0);
        ListNode resHead = q;
        while (pq.size() > 0) {

            q.val = pq.poll();
            if (pq.size() > 0) {

                ListNode temp = new ListNode(0);
                q.next = temp;
            }
            q = q.next;
        }
        return resHead;
    }
}

/*作者：Booooo_
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-you-xian-dui-lie-gui-bi-h3ga/
来源：力扣（LeetCode）
*/

3 总结

链表啊链表，虽然双向链表和环形链表很难、但是基本不考（美滋滋）。单链表的一些考察点凭印象总结一下：

最常用的遍历，如果要用到哪一个结点必须先判断其不为空，，处理完要记得指针后移
最基础的增删改拼接，增加要3点钟顺时针；删除直接改指针；有重复元素时用while删，并且要注意循环内部的结点不能为空（可用一个整型存值判断）
快慢指针解决倒数k结点、找中间元素、环形链表、第一个公共结点问题。要注意每段的长度以及走多少步之后能相遇，草稿列一下公式画一下图；
反转链表常规操作了、反转部分链表注意链表之间的拼接就好（多设几个指针）
重排链表和回文链表，基本就是找中间元素+反转链表的组合题
复制随机指针的链表，遍历两次第一次复制节点值，第二次复制指针
排序链表是归并排序+找中间结点+已排好序的链表拼接的组合题

链表的题目变化还是挺大的、手生了基本做不了、调试也很难通过。多练吧少年！奥里给

4 新的题目

新遇到的常考题或者做不出来的题都会放在这里！！

2. 两数相加

结果链表构造是要用一个移动指针cur 所以要用哑巴节点保存头节点的位置
因为要考虑进位的问题，其实链表之所以个位在前就是方便你进位！！
遍历完两个链表、如果短链表为空了就以0代替之

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(-1);
        ListNode cur = dummyNode;
        int carry = 0; //进位值
        while(l1!=null||l2!=null){
            int n1 = l1!=null? l1.val:0;
            int n2 = l2!=null? l2.val:0;
            int sum = n1+n2+carry;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new ListNode(sum);
            cur = cur.next;

            if(l1!=null)l1 = l1.next;
            if(l2!=null)l2 = l2.next;
        }
        if(carry==1) cur.next = new ListNode(1);
        return dummyNode.next;
    }
}