链表(一)：反转链表全家桶+合并有序链表全家桶

1. 反转链表

1.1 题目

1.2 题解

1.2.1 迭代法

思路：定义cur指针遍历链表，让当前节点的next指向前一个节点，所以需要定义pre保存遍历到的当前节点的前一个节点，还要定义curNext用来保存当前节点的下一个节点，用于cur向后继续遍历
图示：

代码：

 public ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=pre;
            pre=cur;
            cur=curNext;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.2.2 递归法

思路：
递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程，最重要的就是查看能不能讲原本的问题分解为更小的子问题，这是使用递归的关键.
对于本题来说，如果我们先忽略头节点，就可以将反转后续的链表看成是一个子问题

终止条件：到达最后一个节点就返回，同时最后一个节点也是反转后的链表头节点
返回值：每一级返回的都是链表的最后一个节点(反转后链表的头节点)

具体做法：

step1：递归向下到最尾节点
step2：在回归的过程中，改变当前层head和next之间的指向
step3：返回新的头节点

图示：

代码：

 public ListNode ReverseList(ListNode head) {
        if(head==null|| head.next==null){
            return head;
        }
        ListNode next=head.next;
        ListNode ret=ReverseList(head.next);
        next.next=head;
        head.next=null;
        return ret;
    }
1
2
3
4
5
6
7
8
9
10

1.2.3 使用栈

思路：
利用栈先进后出的原理，遍历一遍链表将所有节点都压栈，然后依次弹出并串联在一起，最后让栈中最后一个节点的next指向null

代码：

  public ListNode ReverseList(ListNode head) {
        if(head==null) return null;
        Stack<ListNode> stack=new Stack<>();
        ListNode cur=head;
        while(cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        ListNode ret=stack.pop();
        cur=ret;
        while(!stack.isEmpty()){
            ListNode tmp=stack.pop();
            cur.next=tmp;
            cur=tmp;
        }
        cur.next=null;
        return ret;     
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2. 链表内指定区间反转

2.1 题目

2.2 题解

2.2.1 双指针(两次遍历）

思路：
这一题相当于时反转链表的进阶版，我们只需要找到区间的最左侧节点和区间的最右侧节点，然后调用反转链表的方法，将这段区间反转，最后将该区间与其前后节点连接在一起即可
具体步骤：

step1：第一次遍历，找到区间的最左侧节点的前一个节点定义为pre，同时也就找到了区间的最左侧节点定义为leftNode
step2：第二次遍历，找到区间的最右侧节点rightNode，同时将区间最右侧的节点保存在cur中，用于后续的连接
step3：将区间与其前后节点断开连接
step4：反转区间上的链表
step5：将反转后的区间与其前后节点连接

【注意】：使用虚拟头节点的技巧，可以避免对头节点复杂的分类考虑，简化操作。
图示：

代码：

 public ListNode reverseBetween (ListNode head, int m, int n){
         
        ListNode dummy=new ListNode(-1);
         dummy.next=head;
          ListNode pre=dummy;
          for(int i=0;i<m-1;i++){
              pre=pre.next;
          }
          ListNode leftNode=pre.next;
          ListNode rightNode=dummy;
          for(int i=0;i<n;i++){
              rightNode=rightNode.next;
          }
          ListNode cur=rightNode.next;
          pre.next=null;
          rightNode.next=null;
          ReverseList(leftNode);
          pre.next=rightNode;
          leftNode.next=cur;
          return dummy.next;
 
    }
    private ListNode ReverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=pre;
            pre=cur;
            cur=curNext;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

2.2.2 头插法迭代(一次遍历)

具体步骤：

step1：遍历链表让pre执行待反转区间的最左侧节点的前一个节点，cur指向反转区间的第一个节点
step2：cur.next用来保存tmp的后序节点
step3：定义tmp用来头插，将tmp所指向的节点头插到已经完成反转的区间的头部，每完成一次头插，pre.next都要指向新的头

图示：

代码：

      public ListNode reverseBetween (ListNode head, int m, int n){
         
        ListNode dummy=new ListNode(-1);
         dummy.next=head;
        ListNode pre=dummy;
          ListNode cur=head;
          for(int i=1;i<m;i++){
              pre=cur;
              cur=cur.next;
          }
          for(int i=m;i<n;i++){
              ListNode tmp=cur.next;
              cur.next=tmp.next;
              tmp.next=pre.next;
              pre.next=tmp;
          }
          return dummy.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 链表中的节点每k个一组翻转

3.1 题目

3.2 题解

3.2.1 递归

思路：
假设链表共有n个分组可以反转，先对第一个分组进行反转，让后将剩下的n-1组反转后连接在第一组的后面就可以了，对剩下的n-1组反转就可以看成是一个子问题，因此可以用递归来完成

终止条件：当最后一组的节点个数少于k个，直接返回不需要反转
返回值：返回当前组翻转后的头节点
本级任务：反转当前分组，用反转后的尾连接后面反转好了的链表的头，最后返回当前分组反转完成后的头

图示：

代码：

public ListNode reverseKGroup (ListNode head, int k) {

        ListNode tail=head;
        for (int i = 0; i < k; i++) {
             if(tail==null){
                 return head;
             }
             tail=tail.next;
        }
        ListNode pre=null;
        ListNode cur=head;
        while (cur!=tail){
            ListNode curNext=cur.next;
            cur.next=pre;
            pre=cur;
            cur=curNext;
        }
        head.next=reverseKGroup(tail,k);
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4. 合并两个已排序的链表

4.1 题目

4.2 题解

4.2.1 迭代法

具体步骤：

step1：定义一个哨兵节点dummy作为新链表的头节点，最后在返回时去掉即可
step2：如果l1指向的节点的val小于l2指向的节点的val，就将l1所指向的节点连接到新链表的尾部，然后让l1指向下一个节点
step3：反之，就将l2所指向的节点连接到新链表的尾部，然后让l2指向下一个节点
step4：循环step2和step3，直到l1或l2遍历到链表尾
step5：将l1或l2剩下的部分连接到新链表的尾部

代码：

public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null&&list2==null) return null;
        if(list1==null) return list2;
        if(list2==null) return list1;
       ListNode dummy=new ListNode(-1);
        ListNode ret=dummy;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                dummy.next=list1;
                list1=list1.next;
                dummy=dummy.next;
            }else {
                dummy.next=list2;
                list2=list2.next;
                dummy=dummy.next;
            }
        }
        if(list1!=null) dummy.next=list1;
        if(list2!=null) dummy.next=list2;
        return ret.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

4.2.2 递归法

思路：

要想使用递归，就要看是否能将问题转化成子问题，对于本题来说，先比较两个链表的头节点，较小的那个一定是合并后链表的头，如果l1.val<=l2.val，那么就将问题转化成了合并l1.next和l2这样的子问题，如果l2.val

• 终止条件：l1和l2都为空，返回空；l1和l2其中一个为空，返回不为空的那个
• 返回值：将当前层的两个链表和并之后的头节点
• 本级任务：先比较当前层的两个链表的头节点，较小的那个作为当前层两个链表合并之后的头节点，然后用这个头节点连接后面合并好的链表，最后返回这个头节点

代码：

 public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null && list2==null) return null;
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1.val<=list2.val){
            list1.next=Merge(list1.next,list2);
            return list1;
        }else {  
            list2.next=Merge(list1,list2.next);
            return list2;
        } 
    }
1
2
3
4
5
6
7
8
9
10
11
12

5. 合并k个已排序的链表

5.1 题目

5.2 题解

5.2.1 优先级队列

在上面合并两个有序链表的题目中，我们使用的是双指针遍历的方式，对于本题合并k个链表来说，我们需要准备k个指针，用这k个指针来遍历k个链表，并且需要比较出这k个指针所指向的节点的最小的一个，因此可以使用小根堆来解决，堆顶元素就是队中的最小的元素

具体做法：

step1：在构造优先级队列时，传入比较器，用来指定比较规则
step2：遍历k个链表的头，将不是空的链表头加入堆中
step3：每次弹出堆顶元素，将该节点连接到新链表的尾，如果该节点的后序节点不为空，则将该节点的后序节点加入队中
step4：循环执行step3，直到堆为空

代码：

  public ListNode mergeKLists(ArrayList<ListNode> lists) {
        Queue<ListNode> queue=new PriorityQueue<>(
                (o1,o2)->o1.val-o2.val
        );
        for(int i=0;i<lists.size();i++){
            if(lists.get(i)!=null){
                queue.add(lists.get(i));
            }
        }
        ListNode dummy=new ListNode(-1);
        ListNode ret=dummy;
        while (!queue.isEmpty()){
            ListNode tmp=queue.poll();
            dummy.next=tmp;
            dummy=dummy.next;
            if(tmp.next!=null){
                queue.add(tmp.next);
            }
        }
        return ret.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.2.2 分治法

思路：
假设链表总数为k，每次合并两个链表，经过一轮后，链表数组变为k/2，在经过一轮后链表总数为k/4，直到合并成一个链表为止

图示：

代码：

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        
        return mergeKListsChild(lists,0,lists.size()-1);
    }
    public ListNode mergeKListsChild(ArrayList<ListNode> lists,int L,int R){
         
        if(L==R){
            return lists.get(L);
        }
        if(L>R){
            return null;
        }
        
        int mid=L+(R-L)/2;
        return Merge(mergeKListsChild(lists,L,mid),mergeKListsChild(lists,mid+1,R));
    }
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null && list2==null) return null;
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1.val<=list2.val){
            list1.next=Merge(list1.next,list2);
            return list1;
        }else {  
            list2.next=Merge(list1,list2.next);
            return list2;
        } 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42