反转链表

这是这是这是最最最基础的一个题目，也是出现频率最高的一个题目

感觉每次都是稀里糊涂的把它写出来的，但是过很长时间重新去写的话，又会变得生疏很多

今天痛定思痛，把这一个类型的题目好好梳理一下

反转整个链表

首先我们先来看一看最最最基础的一种方式，反转整个链表，题目详情可见反转链表。这里将给出两种实现方式：「迭代」和「递归」

先介绍迭代吧吧吧吧！！！


// 迭代
public ListNode reverse(ListNode head) {
    ListNode prev, curr, next;
    // 刚刚开始，只有 curr 是有具体值的
    // prev && next 均为空
    prev = null;
    curr = head;
    next = null;
    
    while (curr != null) {
        // 首先我们需要记录下 curr.next 的值
        // 原因：下一步 我们会改变 curr.next 的值，但是原来的 curr.next 的值在后面依然会用到，所以需要记录一下
        next = curr.next;
        // 改变 curr.next 的值指向 prev，反转指针方向
        curr.next = prev;
        
        // 前进：prev, curr 均向前进一步
        prev = curr;
        curr = next;
    }
    return prev;
}

下面介绍第二种递归方式

递归之前，我们需要明确几个要素：明确「当前节点」「该做什么」「什么时候做」「注意返回值」

当前节点：head 节点
该做什么：具体看下图
什么时候做：后序
注意返回值：子链表完成反转后的头节点

执行完reverse(head.next)后，结果如下

此时我们需要对当前节点，也就是 head 节点做的就是：head.next.next = head; head.next = null;


// 递归
public ListNode reverse(ListNode head) {
    // if (head == null) 说明链表为 null
    // if (head.next == null) 说明此时的 head 节点为最后一个节点
    if (head == null || head.next == null) return head;
    // 遍历
    ListNode last = reverse(head.next);
    // 后序
    head.next.next = head;
    head.next = null;
    // 注意：永远返回的是最底层递归的结果。递归中途，返回值是没有改变的
    return last; 
}

反转链表前 N 个元素

先介绍迭代吧吧吧吧！！！

反转前 4 个元素，有没有很相似的感觉，就是改变了结束的最后一个元素。对于反转整个链表，结束元素是最后一个null；而对于反转前N个元素，结束元素是第N + 1个元素，即最初时应该prev = 5

我们需要先进行一个遍历，得到第五个节点

所以迭代的代码稍微修改一下就可以了


// 迭代
public ListNode reverseN(ListNode head, int n) {
    // 获得右边界节点
    ListNode rightNode = null;
    ListNode p = head;
    int count = 0;
    while (p != null) {
        count++;
        if (count == n + 1) {
            rightNode = p;
            break;
        }
        p = p.next;
    }
    ListNode prev, curr, next;
    prev = rightNode;
    curr = head;
    next = null;
    
    // 此处也需要随之变化，到 rightNode 即停止
    while (curr != rightNode) {
        next = curr.next;
        curr.next = prev;
        
        prev = curr;
        curr = next;
    }
    return prev;
}

下面介绍第二种递归方式

「反转链表前N个元素」和「反转整个链表」其实前面都一样，唯一不同的就是结束条件，也就是 base case 不一样

对于「反转整个链表」，base case 为head.next = null；而对于「反转链表前N个元素」，base case 为head.next = the Node of (N+1)th

先直接看代码：


private ListNode successor = null;
public ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        // 记录 the Node of (N+1)th
        // 因为第一个节点最后需要接上去
        successor = head.next;
        return head;
    }
    ListNode last = reverseN(head.next, n - 1);
    head.next.next = head;
    head.next = successor;
    return last;
}

反转链表区间 [m, n] 的元素

题目详情可见反转链表 II

先介绍迭代吧吧吧吧！！！

反转第 2-4 个元素，有没有更加熟悉的感觉，这种情况不仅改变了结束的最后一个元素，而且改变了起始的元素。对于反转整个链表，起始元素是head，结束元素是最后一个null；而对于反转前N个元素，起始元素是head，结束元素是第N + 1个元素；而对于反转区间[m, n]的元素，起始元素是m - 1个元素，结束元素是第n + 1个元素

所以迭代的代码稍微修改一下就可以了


public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode beginNode = null;
    ListNode endNode = null;
    ListNode p = head;
    int count = 0;
    while (p != null) {
        count++;
        if (count == m - 1) beginNode = p;
        if (count == n + 1) {
            endNode = p;
            break;
        }
        p = p.next;
    }
    // 结束元素是第 n+1 个
    ListNode prev = endNode;
    // 结束元素是第 m-1 个
    // 这里需要对一种特殊情况进行判断，即 m=1 的情况
    // 当 m=1 时，beginNode = null
    // 此时起始元素应该直接为 head
    // 否则，起始元素应该为 beginNode.next
    ListNode curr = beginNode == null ? head : beginNode.next;
    ListNode next = null;
    while (curr != endNode) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    // 同理，如果 beginNode = null，「反转后的头节点」直接为 prev，和反转整个链表同理
    // 否在，需要把 beginNode 和「反转后的头节点」连接起来
    if (beginNode == null) return prev;
    beginNode.next = prev;
    return head;
}

下面介绍第二种递归方式

「反转链表区间[m, n]的元素」和「反转链表前N个元素」其实就是开始节点不一样而已

先直接看代码：


xxxxxxxxxx
public ListNode reverseBetween(ListNode head, int m, int n) {
    if (m == 1) {
        // 直接调用 reverseN() 方法
        return reverseN(head, n);
    }
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

K 个一组翻转链表

今天 (2022-04-16 17:06:52) 更新一下本篇文章，新增一个内容，即：K 个一组翻转链表。题目详情可见 K 个一组翻转链表

思考了很久，本来想用迭代的方法去解决它，可是遇到了一个问题。处理第i组的时候无法获得第i + 1组的头节点，如图：

设k = 2，当我们处理节点 1、2 的时候，最后我们需要把 1 -> 4，可是我们在处理 1、2 的时候暂时无法得到 3、4 处理完的头节点 4

很容易可以想到，其实这很类似于二叉树的后续遍历。处理当前节点时，需要用到子问题的结果

直接上代码：


public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null) return null;
    ListNode start = head, end = head;
    for (int i = 0; i < k; i++) {
        // 不满 k 个，直接返回 head
        if (end == null) return start;
        end = end.next;
    }
    // 翻转 [start, end)
    ListNode newHead = reverse(start, end);
    // 翻转后，start 变成了尾节点
    // 尾节点需要指向子问题的头节点
    start.next = reverseKGroup(end, k);
    // 返回当前问题的头节点
    return newHead;
}
// 翻转 [start, end) 区间的链表
private ListNode reverse(ListNode start, ListNode end) {
    ListNode prev = null;
    ListNode curr = start;
    ListNode next = null;
    while (curr != end) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}