（1）什么是链表？

        

（2）链表的类型

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

        

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;
    }
}

        

（3）新增节点

        

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

        

二、题目类型

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

  /**
   * 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】可以看到设置虚拟头节点后，直接统一处理要删除的节点即可，而这部分代码与直接使用原链表对非头部节点的处理一样。

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

  //定义节点
  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--;
      }
  }
  

• 思路一：实现链表元素的反转只需要改变链表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);
  }

• 思路一：令 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;
  }

• 思路一：转为删除链表的正数节点问题。先求出链表长度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;
  }

• 这道题难在理解上。让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;
  }

• 原理：这道题有两大难点，参考代码随想录：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;
  }

• 思路一：双指针遍历给出的两个链表，用一个变量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;
      }
  }

• 思路一：原地合并。

  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;
          }
      }
  }

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

  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;
      }
  }

• 思路一：归并排序+递归。利用归并的思想，递归地将当前链表分为两段，然后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;
      }
  }