一、链表基础

1.理论基础

（1）什么是链表？

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链接的入口节点称为链表的头结点(head)。

（2）链表的类型

单链表
双链表
单链表中的指针域只能指向节点的下一个节点。双链表的每一个节点有两个指针域：一个指向下一个节点，一个指向上一个节点。双链表既可以向前查询也可以向后查询。
循环链表
循环链表就是链表首尾相连，可以用来解决约瑟夫环问题。

（3）链表在内存中的存储方式

数组是在内存中是连续存储的，而链表在内存中是不连续存储的。

链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续存储的，而是散乱存储在内存中的某地址上，分配机制取决于操作系统的内存管理。

如下图所示，这个链表起始节点为2，终止节点为7，各个节点存储在内存的不连续地址空间上，通过指针串联在一起。

2.链表的操作

（1）定义一个链表节点

//定义节点
public class ListNode {
    // 节点的两部分组成：结点的值 和 下一个结点
    int val;
    ListNode next;
    
    // 节点的构造函数(无参)
    public ListNode() {
    }
    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }
    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

（2）删除节点

删除非头结点：删除D节点(如图所示)，只要将C节点的next指针指向E节点即可。

删除头结点：因为单链表只能指向下一个节点，同时链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点，所以对头结点的处理与其他节点不同。那么如何删除头结点呢？
- 法一：直接使用原来的链表来进行删除操作，此时只需要将头结点移动到下一个节点，就可以从链表中移除一个头结点。
- 法二(推荐)：设置一个虚拟头结点(dummy node)再进行删除操作，这样原链表的所有节点(包括头结点)就都可以按照统一的方式进行移除了。
  
  【tips】但是真正的头结点是：dummyNode->next。

（3）新增节点

新增F节点，只需要将F节点的next指针指向D节点，再讲C节点的next指针指向F节点即可。

可以看出链表的增和删都是O(1)操作，不会影响到其他节点。但如果是删除最后一个节点，需要从头节点查找到第四个节点通过next指针进行删除操作，查找的时间复杂度是O(n)。

3.链表与数组的性能对比

数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。

链表的长度可以是不固定的，并且可以动态增删，适合数据量不固定，频繁增删，较少查询的场景。

二、题目类型

1. 203. 移除链表元素

思路一：直接使用原链表，需要对删除头结点单独处理。细节多，麻烦，不推荐。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //先删除值等于val的头结点
        while(head!=null&&head.val==val){//★这里要写上head!=null，因为head等于空时根本没有val，会报错！
            head=head.next;
        }
        //★空链表 或者 所有节点值都等于val的情况，经while循环后head也是=null
        if(head==null){
            return head;
        }
        //head.val肯定不等于val了
        //★前一个节点和当前节点，因为head.val肯定不等于val了，所以从head的下一个节点开始处理，因此当前节点初始值是head.next
        ListNode pre=head;
        ListNode curr=head.next;
        //遍历链表
        while(curr!=null){
            //如果当前节点的val==val，删除当前节点，把当前节点的上一个节点的next指向当前节点的下一个节点，当前节点后移
            if(curr.val==val){
                pre.next=curr.next;
            }else{//如果当前节点的值不等于val，上一个节点和当前节点都后移
                pre=curr;
            }
            curr=curr.next;
        }
        return head;
    }
}

思路二(推荐)：设置虚拟头节点，对所有节点的删除处理都一样，返回的头结点是虚拟头节点的下一个节点。

public ListNode removeElements(ListNode head, int val) {
    //创建一个虚拟节点
    ListNode dummyNode=new ListNode(-1,head);
    //前一个节点和当前节点
    ListNode pre=dummyNode;
    ListNode curr=head;
    //遍历链表
    while(curr!=null){
        if(curr.val==val){
            pre.next=curr.next;
        }else{
            pre=curr;
        }
        curr=curr.next;
    }
    return dummyNode.next;
}

【tips】可以看到设置虚拟头节点后，直接统一处理要删除的节点即可，而这部分代码与直接使用原链表对非头部节点的处理一样。

2. ★707. 设计链表

这道题目涵盖了链表的常见操作：获取指定节点的值、删除节点、插入节点(头、尾、中间)。所有操作全采用虚拟头结点来做。

//定义节点
class ListNode{
    //当前节点的值
    int val;
    //指向下一个节点的指针
    ListNode next;
    //无参构造
    public ListNode(){};
    //两个带参构造
    public ListNode(int val){
        this.val = val;
    }
    public ListNode(int val,ListNode next){
        this.val = val;
        this.next=next;
    }
        //没用到get/set方法，所以不用定义
}
//定义单链表
class MyLinkedList {
    //链表节点数，★用来判断index是否合法
    int size;
    //★虚拟头节点，因为初始单链表里面是没有节点的，所以这个head是虚拟头结点。
    ListNode head;
    //★构造方法，初始化链表：长度为0，因为head为虚拟头节点因此head的next不用给，★也不能是null！(虚拟头结点嘛，next应该是真正的head，但是初始化时没有头，所以next不给。)
    public MyLinkedList(){
        head=new ListNode();//虚拟头结点的值随便给，不给也行
        size=0;
    }
    //获取链表中第 index 个节点的值。如果索引无效，则返回-1。【★注意虚拟头结点不算在index内，头结点才是第0个节点，所以index也不能等于size！】
    public int get(int index) {
        //索引无效，返回-1
        if(index<0||index>=size){
            return -1;
        }
        ListNode curNode=head.next;
        //找第index个节点
        for(int i=0;i<index;i++){//关于循环条件的判断：通过找极端情况，看当index=0时(即返回头结点val)是否成立。
            curNode=curNode.next;
        }
        return curNode.val;
    }
    //在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    //将值为 val 的节点追加到链表的最后一个元素。
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    //在链表中的第index个节点之前添加值为val的节点:如果index等于链表长度,则该节点将附加到链表的末尾;如果index大于链表长度,则不会插入节点(即返回空);如果index小于0,则在头部插入节点
    public void addAtIndex(int index, int val) {
        //index 大于链表长度，则不会插入节点
        if(index>size){
            return;
        }
        //★index小于0，则在头部插入节点，即在第0个节点前插入新节点，所以index<0等价于index=0。
        if(index<0){
            index=0;
        }
        //初始化第0个节点的前一个节点
        ListNode preNode=head;
        //找第index个节点的前一个节点
        for(int i=0;i<index;i++){//在第 index 个节点前插，所以不能=index
            preNode=preNode.next;
        }
        //创建新节点
        ListNode newNode=new ListNode(val);
        //插入新节点
        newNode.next=preNode.next;
        preNode.next=newNode;
        //插入成功，size++
        size++;
    }
    //如果索引 index 有效，则删除链表中的第 index 个节点。
    public void deleteAtIndex(int index) {
        //索引无效，直接返回
        if(index<0||index>=size){
            return;
        }
        //初始化第0个节点的前一个节点
        ListNode preNode=head;
        //找第 index 个节点的前一个节点
        for(int i=0;i<index;i++){
            preNode=preNode.next;
        }
        //删除节点
        preNode.next=preNode.next.next;
        //删除成功，size--
        size--;
    }
}

3. ★206. 反转链表

思路一：实现链表元素的反转只需要改变链表next指针的指向，直接将链表反转。要进行节点反转，就需要知道上一个节点、当前节点以及反转后要移动到下一个节点，因此我们先定义两个指针pre和cur，分别指向上一个节点和当前要反转的节点；反转完该节点后，因为该节点的next已经指向上一个节点了，这样就找不到它的下一个节点了，所以我们定义了一个临时节点，在反转节点前先来暂存它的下一个节点。

public ListNode reverseList(ListNode head) {
    ListNode pre=null;
    ListNode cur=head;
    //临时节点
    ListNode temp=null;
    while(cur!=null){
        //★保存当前节点的下一个节点。因为单链表的节点只能通过指针获得，而如果将cur.next指向pre后，就没有指针指向原来cur的下一个节点了，无法进行cur的后移了，因此需要这样一个临时节点来暂存cur的下一个节点。
        temp=cur.next;
        //反转节点
        cur.next=pre;
        //pre和cur后移
        pre=cur;
        cur=temp;
    }
    return pre;
}

思路二：递归法。

public ListNode reverseList(ListNode head) {
    return reverseNode(null,head);//  ★这里当前节点是头结点，反转后成为最后一个节点，所以指向的前一个节点是null
}
// 反转当前节点cur和前一个节点pre public ListNode reverseNode(ListNode pre,ListNode cur){
    // 递归结束的条件
    if(cur==null){
        return pre;
    }
    // 暂存下一个节点
    ListNode temp=cur.next;
    // 反转
    cur.next=pre;
        //  移动指针
    return reverseNode(cur,temp);
}

4. 24. 两两交换链表中的节点

思路一：令 temp 表示当前两两交换的双节点子链的虚拟头结点(即每次需要交换 temp 后面的两个节点)，初始时 temp = dummyHead。
             具体实现：
                    如果 temp 的后面没有节点或者只有一个节点，则没有更多的节点需要交换，因此结束交换。
                    否则，获得 temp 后面的两个节点 first 和 second，即交换之前的节点关系是 temp -> first -> second，交换之后的节点关系要变成 temp -> second -> first；再令 temp = first，一个双节点子链交换完。
                    对链表中的其余节点进行两两交换，直到全部节点都被两两交换。
                    两两交换链表中的节点之后，新链表的头节点是 dummy.next，返回即可。

public ListNode swapPairs(ListNode head) {
    //虚拟头结点，用来获取头结点：dummy.next=head
    ListNode dummy=new ListNode(-1);
    dummy.next=head;
    //用来在每次交换节点时代替虚拟头结点的作用。因为虚拟头结点是用来返回最后的头结点的，不能在交换节点时移动它，所以需要用temp来代替。
    ListNode temp=dummy;
    //至少有两个节点才可以交换
    //交换临时虚拟头结点后的两个节点
    while(temp.next!=null&&temp.next.next!=null){
        //上面的循环条件同时保证了first和second不为空
        ListNode first=temp.next;
        ListNode second=first.next;
        //交换temp后的两个节点
        first.next=second.next;
        second.next=first;
        //★将上一次两两交换后的链表与这一次链表联系起来！
        temp.next=second;
        //将temp后移两个位置
        temp=first;
    }
    return dummy.next;
}

思路二：递归法。递归法的三个问题：终止条件、返回值、单次过程，其实就是搞清楚原来的函数返回的是什么?函数作用是什么？再找准终止条件即可。这道题终止条件很明显：当链表为空或者链表只有一个节点时终止。而这个swapPairs()函数的作用就是交换以形参为第一个节点的两个节点，并返回交换后的头结点。至此递归的三个问题我们搞清楚了。
具体实现：我们将前三个节点当成one、two、three三个节点，那么就有one=head，two=one.next，three=two.next，这样更好理解一点。

//★swapPairs(ListNode head)的意义就是交换以head为头结点的两个节点，并返回交换后的新的头结点。
public ListNode swapPairs(ListNode head) {
    //终止条件
    if(head==null||head.next==null){
        return head;
    }
    //one->two->three->...
    ListNode one=head;
    ListNode two=one.next;
    ListNode three=two.next;
    //交换节点one和two
    two.next=one;
    one.next=swapPairs(three);//★one.next应该是下一组两两交换后的新的头结点，所以通过swapPairs来返回这个新的头结点。
    //返回头结点：交换后的头结点一定是第二个节点
    return two;
}

5. 19.删除链表的倒数第N个节点

思路一：转为删除链表的正数节点问题。先求出链表长度size，那么删除倒数第n个节点等价于删除正数第(size-n)个节点(头结点为第0个节点)。

public ListNode removeNthFromEnd(ListNode head, int n) {
    //题目已规定n一定有效
    //虚拟头结点
    ListNode dummy=new ListNode(-1);
    dummy.next=head;
    //循环指针
    ListNode temp=new ListNode(-1);
    temp.next=head;
    //链表长度
    int size=0;
    while(temp.next!=null){
        temp=temp.next;
        size++;
    }
    //删除倒数第n个节点即删除正数第(size-n)个节点(从0开始算)
    int index=size-n;
    ListNode pre=dummy;
    ListNode cur=dummy.next;
    for(int i=0;i<index;i++){
        pre=pre.next;
        cur=cur.next;
    }
    //删除节点
    pre.next=cur.next;
    return dummy.next;
}

思路二：★双指针法。因为删除节点需要知道前一个节点，所以可以利用双指针，让两个指针始终保持相距(n+1)个位置（因为只有这样同时移动的时候slow才能指向删除节点的上一个节点，方便做删除操作），然后同时移动，这样当快指针为空时，慢指针刚好指向要删除节点的前一个节点。

public ListNode removeNthFromEnd(ListNode head, int n) {
    //因为删除节点一定是需要知道前一个节点的，所以可以利用双指针，让两个指针保持相距(n+1)个位置的同时移动，这样当快指针为空时，慢指针刚好指向要删除节点的前一个节点。
    ListNode dummy=new ListNode(-1);
    dummy.next=head;
    //初始化双指针为虚拟头结点
    ListNode fast=dummy;
    ListNode slow=dummy;
    //先让快指针走n+1，这样就保证了后面双指针同时移动时二者始终保持n+1的距离在移动。
    for(int i=1;i<=n+1;i++){
        fast=fast.next;
    }
    //同时移动双指针，直到快指针为空，这时慢指针一定指在要删除节点的前一个节点
    while(fast!=null){
        fast=fast.next;
        slow=slow.next;
    }
    //删除节点
    slow.next=slow.next.next;
    return dummy.next;
}

6. 面试题 02.07. 链表相交/160. 相交链表

这道题难在理解上。让pA指向链表A的头，pB指向链表B的头，然后分别用它们遍历两个链表，遍历完自己的链表后再从头开始遍历另一条链表，此时pA和pB是在“同一位置上”移动了，这样如果有交点，pA和pB就会相遇，返回交点；如果再遍历完，说明没交点，返回空。
具体实现：
当pA不为空，则将pA移到下一个节点；当pB不为空，则将pB移到下一个节点；
如果pA为空，说明链表A遍历完了，则将pA 移到链表B的头节点；如果pB 为空，说明链表B遍历完了，则将pB移到链表A的头节点；
★当pA和pB指向同一个节点或者都为空时，返回它们指向的节点或者null。(这也是为什么循环条件是pA!=pB，以及if判断是pA==null而不是pA.next==null，两个条件要一致)
现在来解释一下为什么要先遍历自己再遍历别人：
        第①种情况——相交：那么相交部分节点数为c，不相交部分链表A有a个节点，链表B有b个节点。现在开始遍历：
              1）a≠b：pA和pB在第一次遍历各自链表时不会相遇，pA遍历完链表A走了(a+c)个节点，再从链表B开始走b个节点，共走了(a+c+b)个节点；同理，pB遍历完链表B走了(b+c)，再从链表A的头走a，共走了(b+c+a)个节点，显然a+c+b=b+c+a，所以现在二者在交点相遇。
              2）a=b：pA和pB在第一次遍历就相遇在交点了。

        第②种情况——不相交：因为循坏条件是pA != pB，同时又没有交点，所以无论链表A、B长度是否相同，最终都会同时变为null，不满足进入循环的条件然后退出循环，返回的也就是null了。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 任一链表为空，则必不存在相交节点
    if(headA==null||headB==null){
        return null;
    }
    ListNode pA=headA;
    ListNode pB=headB;
        //退出循环的条件时pA=pB，要注意：如果存在交点，那么最终pA=pB=交点退出循环，返回交点；如果不存在交点，pA和pB一定是遍历完自己和对方后，同时到达null，所以还是pA=pB=null退出循环，返回空。
    while(pA!=pB){
        pA=pA==null?headB:pA.next;
        pB=pB==null?headA:pB.next;
    }
    return pA;
}

7. ★142.环形链表II

原理：这道题有两大难点，参考代码随想录：https://www.programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#_142-%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8ii
(一)如何判断是否有环？
——可以使用双指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针相遇，说明这个链表有环。同时，如果二者能相遇，那么一定是在环内相遇，因为fast走的快，一定会在未相遇前先进入环。

(二)若有环，如何找入环节点？
——fast和slow在环内相遇后，再令定义两个指针index1=相遇节点和index2=head，让index1和index2同时移动，每次走一步，那么二者相遇的节点，就是入环节点。

思路：解决了以上两个问题后，代码就好写了：

public ListNode detectCycle(ListNode head) {
        //从头结点出发
    ListNode fast=head;
    ListNode slow=head;
        //至少有两个节点时才可能有环。如果连这个条件都不满足，不进while，直接return null
    while(fast!=null && fast.next!=null){
                //快指针每次走两步，慢指针每次走一步
        fast=fast.next.next;//上面的循环条件同时也保证了fast.next.next有效。
        slow=slow.next;
        if(fast==slow){//有环，环内相遇
            //找入环节点，分别从头结点和相遇节点开始走
            ListNode idx1=head;
            ListNode idx2=fast;
            while(idx1!=idx2){
                idx1=idx1.next;
                idx2=idx2.next;
            }
                        //返回入环节点
            return idx1;
        }
    }
    //fast==null了，也无环
    return null;
}

8.2. 两数相加

思路一：双指针遍历给出的两个链表，用一个变量flag判断上一次是否有进位(即本次需不需要加1)，同时要判断本次相加后需不需要向后进位。而且如果两链表长度不同，剩下的直接移到新链表上即可。注意要判断最后一次需不需要进位，如果需要进位，还要再创建一个值为1的节点。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //有一个为空，结果就是另一个链表
        if(l1==null) return l2;
        if(l2==null) return l1;
        //双指针，用来遍历两个链表
        ListNode p1=l1;
        ListNode p2=l2;
        ListNode dummyNode=new ListNode();
        ListNode pre=dummyNode;
        //用来判断上一个节点是否进位了
        boolean flag=false;
        //只要有一个为空，跳出while
        while(p1!=null&&p2!=null){
            int sum=p1.val+p2.val;
            ListNode node=new ListNode();
            if(flag){
                sum+=1;
            }
            //不需要进位
            if(sum<10){
                node.val=sum;
                flag=false;
            }else{
                //需要进位,最多进1
                node.val=sum%10;
                flag=true;
            }
            pre.next=node;
            pre=node;
            p1=p1.next;
            p2=p2.next;
        }
        //链表长度不同时
        while(p1!=null){
            ListNode node=new ListNode();
            int sum=p1.val;
            if(flag){
                sum+=1;
            }
            if(sum<10){
                node.val=sum;
                flag=false;
            }else{
                node.val=sum%10;
                flag=true;
            }
            pre.next=node;
            pre=node;
            p1=p1.next;
        }
        while(p2!=null){
            ListNode node=new ListNode();
            int sum=p2.val;
            if(flag){
                sum+=1;
            }
            if(sum<10){
                node.val=sum;
                flag=false;
            }else{
                node.val=sum%10;
                flag=true;
            }
            pre.next=node;
            pre=node;
            p2=p2.next;
        }
        //对最后一次是否进位的判断
        if(flag){
            ListNode node=new ListNode(1);
            pre.next=node;
        }
        return dummyNode.next;
    }
}

★优化：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1), pre = dummyHead;
        int t = 0;
        while (l1 != null || l2 != null || t != 0) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            pre.next = new ListNode(t % 10);
            pre = pre.next;
            t /= 10;
        }
        return dummyHead.next;
    }
}

9.21. 合并两个有序链表

思路一：原地合并。

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1==null) return list2;
    if(list2==null) return list1;
    ListNode dummy=new ListNode();
    ListNode cur=dummy;
    while(list1!=null&&list2!=null){
        if(list1.val<=list2.val){
            cur.next=list1;
            cur=cur.next;
            list1=list1.next;
        }else{
            cur.next=list2;
            cur=cur.next;
            list2=list2.next;
        }
    }
    if(list1==null){
        cur.next=list2;
    }
    if(list2==null){
        cur.next=list1;
    }
    return dummy.next;
}

思路二：递归。

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1.val<=list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next=mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

10.23. 合并 K 个升序链表

思路一：优先级队列——小顶堆。

class Solution {
    //lists里放的是各个链表的头结点!
    public ListNode mergeKLists(ListNode[] lists) {
        int k=lists.length;
        if(lists==null||k==0) return null;
        //小顶堆(从队头到队尾递减)
        // PriorityQueue<ListNode> pq=new PriorityQueue<>(new Comparator<ListNode>(){
        //     @Override
        //     public int compare(ListNode o1,ListNode o2){
        //         return o1.val-o2.val;
        //     }
        // });
        PriorityQueue<ListNode> pq=new PriorityQueue<>((o1,o2)->o1.val-o2.val);
        //先把k个链表的每个头结点放入pq
        for(ListNode list:lists){
            //★注意判断list为空的情况
            if(list!=null){
                pq.offer(list);
            }
        }
        ListNode dummyNode=new ListNode(-1);
        ListNode cur=dummyNode;
        while(!pq.isEmpty()){
            ListNode newNode=pq.poll();
            cur.next=newNode;
            cur=cur.next;
            //始终维护容量为k的小顶堆
            if(newNode.next!=null){
                pq.offer(newNode.next);
            }
        }
        return dummyNode.next;
    }
}

思路二：★分治。将k个链表两两合并，一轮后再两两合并，直到最后只剩下一个链表。

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k=lists.length;
        //★分治终止条件
        //1.lists为空
        //2.lists只有一个链表头结点，直接返回该头结点
        //3.lists只有两个链表的头结点，返回合并这两个头结点
        if(lists==null||k==0) return null;
        if(k==1) return lists[0];
        if(k==2) return merge2Lists(lists[0],lists[1]);
        //2路归并
        int mid=k/2;
        //分治(分成两组)
        ListNode[] l1=new ListNode[mid];
        for(int i=0;i<mid;i++){
            l1[i]=lists[i];
        }
        ListNode[] l2=new ListNode[k-mid];
        for(int i=0;i<k-mid;i++){
            l2[i]=lists[mid+i];
        }
        //归并(★每组再分治再合并)
        return merge2Lists(mergeKLists(l1),mergeKLists(l2));
    }
    //合并两个有序链表
    public ListNode merge2Lists(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode();
        ListNode cur=dummy;
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                cur.next=l1;
                cur=cur.next;
                l1=l1.next;
            }else{
                cur.next=l2;
                cur=cur.next;
                l2=l2.next;
            }
        }
        if(l1==null){
            cur.next=l2;
        }else{
            cur.next=l1;
        }
        return dummy.next;
    }
}

11.★148. 排序链表

要求：O(nlogn) 时间复杂度、O(1)空间复杂度。看到O(nlogn)的时间复杂度，首先要想到用归并和快排。对数组的常规归并需要额外创建数组，满足不了O(1)的空间复杂度，但是对链表的归并可以不使用递归来实现O(1)的空间复杂度。

思路一：归并排序+递归。利用归并的思想，递归地将当前链表分为两段，然后merge。分两段的方法是使用快慢指针找中间位置。merge时，就是合并两个有序链表的知识了。

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    //归并排序
    public ListNode mergeSort(ListNode head){
        //没有节点或只有一个节点，不需要排序，直接返回
        if(head==null||head.next==null) return head;
        //快慢指针
        ListNode slow=head,fast=head;
        //★用来记录中点的上一个节点，即左半部分链表的最后一个节点
        ListNode last=null;
        while(fast!=null&&fast.next!=null){
            last=slow;
            fast=fast.next.next;
            slow=slow.next;
        }
        //★断链——将左半部分最后一个节点的next置为空，以此来断开原链表
        last.next=null;
        //对左、右半链表进行归并排序
        ListNode left=mergeSort(head);
        ListNode right=mergeSort(slow);
        //合并
        return mergeList(left,right);
    }
    //合并两个链表
    public ListNode mergeList(ListNode left,ListNode right){
        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                cur.next=left;
                cur=cur.next;
                left=left.next;
            }else{
                cur.next=right;
                cur=cur.next;
                right=right.next;
            }
        }
        if(left==null){
            cur.next=right;
        }else{
            cur.next=left;
        }
        return dummy.next;
    }
}

★思路二：归并+自底向上。自底向上的归并思路是：先两个两个的 merge，完成一趟后，再 4 个4个的 merge，...，直到结束。
举例：对于[4,3,1,7,8,9,2,11,5,6]，

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        //计算链表长度
        ListNode p=head;
        int len=0;
        while(p!=null){
            len++;
            p=p.next;
        }
        //虚拟头结点
        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        //每次将链表拆分成若干个长度为step的子链表，并两两合并
        for(int step=1;step<len;step*=2){
            ListNode pre=dummy,cur=dummy.next;
            //★每次循环生成l1、l2、left三条链，将l1和l2合二为一，下一次循环对left进行重复处理
            while(cur!=null){
                ListNode l1=cur;
                //★将cur移动到当前子串末尾!注意不是下一个子串开头，因为这样就没法断链了(cur.next=null)!
                for(int i=1;i<step && cur!=null && cur.next!=null;i++){
                    cur=cur.next;
                }
                ListNode l2=cur.next;
                //断链
                cur.next=null;
                cur=l2;
                for(int i=1;i<step && cur!=null && cur.next!=null;i++){
                    cur=cur.next;
                }
                ListNode left=null;
                //★记得判断!
                if(cur!=null){
                    left=cur.next;
                    cur.next=null;
                }
                cur=left;
                ListNode merged=mergeList(l1,l2);
                //★pre的作用:将上次合并链表与这次合并的链表连接起来!
                pre.next=merged;
                //pre移动到本次合并后的链表尾部
                while(pre.next!=null){
                    pre = pre.next;
                }
            }
        }
        return dummy.next;
    }
    //合并两个链表
    public ListNode mergeList(ListNode left,ListNode right){
        ListNode dummy=new ListNode(-1);
        ListNode cur=dummy;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                cur.next=left;
                cur=cur.next;
                left=left.next;
            }else{
                cur.next=right;
                cur=cur.next;
                right=right.next;
            }
        }
        if(left==null){
            cur.next=right;
        }else{
            cur.next=left;
        }
        return dummy.next;
    }
}

思路三：快速排序。

class Solution {
    public ListNode sortList(ListNode head) {
        return quickSort(head);
    }
    public ListNode quickSort(ListNode head) {
        if (head==null || head.next==null) return head;
        //用中间节点的原因是，如果每次用最左边的结点，对于纯递增和纯递减的case就退化为O(n)
        //以中间节点作为pivot，链表可被分为三个子链，即l1:小于pivot、l2:等于pivot、l3:大于pivot
        int pivot = getMid(head).val;
        //★分别定义三个子链的头l(虚拟头)和尾t
        ListNode l1 = new ListNode();
        ListNode l2 = new ListNode();
        ListNode l3 = new ListNode();
        ListNode t1 = l1;
        ListNode t2 = l2;
        ListNode t3 = l3;
        ListNode curr = head;
        //遍历链表节点并与pivot比较，将节点放到对应子链l中
        while (curr!=null) {
            ListNode next = curr.next;
            if (curr.val < pivot) {
                curr.next = null;
                t1.next = curr;
                t1 = t1.next;
            } else if (curr.val == pivot) {
                curr.next = null;
                t2.next = curr;
                t2 = t2.next;
            } else {
                curr.next = null;
                t3.next = curr;
                t3 = t3.next;
            }
            curr = next;
        }
        //对l1和l3分别进行递归快排
        l1 = quickSort(l1.next);
        l3 = quickSort(l3.next);
        //★l1和l3不一定有元素，l2一定有元素(至少是pivot)，所以先将l2和l3连起来(为什么先连l2和l3呢？因为l3为空相当于l2最后一个节点->null)。
        l2 = l2.next;//此时的l2是真正的头节点了
        t2.next = l3;
        //★如果l1链表为空，直接返回l2
        if (l1==null) {
            return l2;
        } else {
            // 否则找到l1的结尾，连上l2的头，返回l1
            t1 = l1;
            // 找到t1链表的结尾
            while (t1.next!=null) {
                t1 = t1.next;
            }
            t1.next = l2;
            return l1;
        }
    }
    //找中间节点
    public ListNode getMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

12.

链表系列