链表反转

数据结构与算法

一、反转整个链表

反转整个链表是leetcode第206题,题目表述：
反转一个单链表。

反转链表有三种方式：
1、递归 2、迭代 3、头插法
递归需要有额外的递归栈空间，空间复杂度O(n)，头插法需要一个额外的虚拟头部，迭代不需要额外的空间，但是实现相对更加复杂。

// 递归 
public ListNode revert(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 不要陷入递归细节，而应该按递归函数定义整体理解
    ListNode last = revert(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}
// 迭代
public ListNode revert(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;
    while(cur != null) {
        // 先保存下一个节点，防止断链
        next = cur.next;
        // 反转
        cur.next = pre;
        // 移动指针
        pre = cur;
        cur = next;
    }
    return pre;
}
// 头插法
public ListNode revert(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 虚拟头部
    ListNode newHead = new ListNode(-1);
    ListNode next = null;
    while(head != null) {
        // 先保存下一个节点，防止断链
        next = head.next;
        head.next = newHead.next;
        newHead.next = head;
        head = next;
    }
    return newHead.next;
}

二、反转链表的前n个节点

题目描述：
将链表的前n个节点进行反转（1 <= n <= 链表长度）

同样有三种实现方式：递归、迭代和头插法

// 递归
// 递归结束之后要连接剩余节点，所以要额外一个变量记录剩余节点
ListNode sucessor = null; //记录后驱节点
public ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        sucessor = head.next;
        return head;
    }
    ListNode last = reverseN(head.next, n - 1);
    head.next.next = head;
    head.next = sucessor;
    return last;
}

// 迭代
public ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        return head;
    }
    ListNode pre = null;
    ListNode cur = head;
    ListNode next = null;
    while (cur != null && n >= 1) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
        n--;
    }
    head.next = next;
    return pre;
}

// 头插法
public ListNode reverseN(ListNode head, int n) {
    if (n == 1) {
        return head;
    }
    // 虚拟头部
    ListNode newHead = new ListNode(-1);
    ListNode cur = head;
    ListNode next = null;
    while(cur != null && n >= 1) {
        next = cur.next;
        cur.next = newHead.next;
        newHead.next = cur;
        cur = next;
        n--;
    }
    head.next = next;
    return newHead.next;
}

三、反转区间的链表节点

leetcode第92题，题目表述：
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。1 ≤ m ≤ n ≤ 链表长度。

思考：如果m=1, 则问题退化为反转链表的前n个节点。所以可以向右移动节点知道m的位置，以此节点为头节点进行反转

    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 如果m=1 问题退化为反转链表的前n个节点
        if (m == 1) {
            return reverseNR(head, n);
        }
        // 转化为子问题(右移节点，区间变动直到m=1，完成问题的退化)
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

四、k个一组反转链表

leetcode第25题，题目表述：
给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。

递归思考：
当我们将链表的前k个节点反转之后，剩下的工作是k个一组反转剩余链表。可以看到剩余工作完全不变，只是规模减小，即递归子问题。
而递归出口就是题目中所说的“如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序”。

如果要进行实现，首先要解决的是k个节点的反转，k个节点反转可以认为是区间反转，但是区间反转结束之后要能够将链表重新连接起来，所以为了简单操作，不再以下标的[m,n]来做为参数，而是以边界节点[a,b)做为参数，这样可以方便链表的前后连接，所以反转函数如下：

// 反转a到b区间内的节点 (注意是左闭右开)
// 可以看到这部分代码和反转整个链表非常相似，实际上反转整个链表可以看作是反转head到null区间[head, null)的节点
public ListNode revertBetween(ListNode a, ListNode b) {
    ListNode pre = null;
    ListNode cur = a;
    ListNode next = null;
    while (cur != b) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

有了反转k个节点的函数之后，然后进行整个链表反转的工作：

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode a = head;
    ListNode b = head;
    // 构造[a, b)的区间，即a到b中间有k个节点(包含a但不包含b)
    for (int i = 0; i < K; i++) {
        if (b == null) {
            return head;   
        }
        b = b.next;
    }
    ListNode newHead = revertBetween(a, b);
    a.next = reverseKGroup(b, k);
    return newHead;
}