链表的多种翻转算法java版（由浅入深，逐个击破）_虚拟头节点java实现链表翻转

前言：

本文先从链表的翻转算法和链表两两交换的算法讲起，最后糅合起来讲解K个一组的链表翻转算法。

1、206. 反转链表

问题描述：

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

题解：

1、利用外部空间：

这种方式很简单，先申请一个动态扩容的数组或者容器，比如 ArrayList 这样的。然后不断遍历链表，将链表中的元素添加到这个容器中。再利用容器自身的 API，反转整个容器，这样就达到反转的效果了。最后同时遍历容器和链表，将链表中的值改为容器中的值。因为此时容器的值是：5 4 3 2 1。链表按这个顺序重新被设置一边，就达到要求啦。
当然你可以可以再新创建 N 个节点，然后再返回，这样也可以达到目的。
这种方式很简单，但你在面试中这么做的话，面试官 100% 会追问是否有更优的方式，比如不用外部空间。很简单所以我就不做代码演示了，下面来看看如何用 O(1)O(1) 空间复杂度来实现这道题。

2、双指针迭代

我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
动画演示如下：

动画演示中其实省略了一个tmp变量，这个tmp变量会将cur的下一个节点保存起来，考虑到一张动画放太多变量会很混乱，所以我就没加了，具体详细执行过程，请点击下面的幻灯片查看。

 代码实现：

class Solution {
	public ListNode reverseList(ListNode head) {
		//申请节点，pre和 cur，pre指向null
		ListNode pre = null;
		ListNode cur = head;
		ListNode tmp = null;
		while(cur!=null) {
			//记录当前节点的下一个节点
			tmp = cur.next;
			//然后将当前节点指向pre
			cur.next = pre;
			//pre和cur节点都前进一位
			pre = cur;
			cur = tmp;
		}
		return pre;
	}
}

3、递归解法

这题有个很骚气的递归解法，递归解法很不好理解，这里最好配合代码和动画一起理解。
递归的两个条件：

1、终止条件是当前节点或者下一个节点==null
2、在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句

head.next.next = head;

很不好理解，其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。
动画演示如下：

代码实现：

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点（reverseList表示：我子节点下的所有节点都已经反转好了，现在就剩我和我的子节点 没有完成最后的反转了）
        ListNode cur = reverseList(head.next);
        //这里请配合动画演示理解
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }
}

参考资料：https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

 

2、两两交换链表中的节点

问题描述：

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例:

给定 1->2->3->4, 你应该返回 2->1->4->3.

题解：

1、递归

这个题目要求我们从第一个节点开始两两交换链表中的节点，且要真正的交换节点。

算法：

从链表的头节点 head 开始递归。
每次递归都负责交换一对节点。由 firstNode 和 secondNode 表示要交换的两个节点。
下一次递归则是传递的是下一对需要交换的节点。若链表中还有节点，则继续递归。
交换了两个节点以后，返回 secondNode，因为它是交换后的新头。
在所有节点交换完成以后，我们返回交换后的头，实际上是原始链表的第二个节点。

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
 
        // If the list has no node or has only one node left.
        if ((head == null) || (head.next == null)) {
            return head;
        }
 
        // Nodes to be swapped
        ListNode firstNode = head;
        ListNode secondNode = head.next;
 
        // Swapping
        firstNode.next  = swapPairs(secondNode.next);
        secondNode.next = firstNode;
 
        // Now the head is the second node
        return secondNode;
    }
}

上面这个是官方的题解答案，我自己更倾向于这样写：

/**
 * 递归的方案2
 *
 * @param head
 * @return
 */
public ListNode swapPairs1(ListNode head) {
    // If the list has no node or has only one node left.
    if ((head == null) || (head.next == null)) {
        return head;
    }
    // Nodes to be swapped
    ListNode firstNode = head;
    ListNode secondNode = head.next;
    ListNode temp = secondNode.next;
    secondNode.next = firstNode;
    // Swapping
    firstNode.next = swapPairs1(temp);
 
    // Now the head is the second node
    return secondNode;
}

后来想了一下，其实我这种还是for循环的递归版的变种，哈哈，但是更好理解。

2：迭代

我们把链表分为两部分，即奇数节点为一部分，偶数节点为一部分，A 指的是交换节点中的前面的节点，B 指的是要交换节点中的后面的节点。在完成它们的交换，我们还得用 prevNode 记录 A 的前驱节点。

算法：

1、firstNode（即 A） 和 secondNode（即 B） 分别遍历偶数节点和奇数节点，即两步看作一步。
2、交换两个节点：

firstNode.next = secondNode.next; 
secondNode.next = firstNode;

3、还需要更新 prevNode.next 指向交换后的头。

prevNode.next = secondNode;

4、迭代完成后得到最终的交换结果。

代码实现：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * 非递归的
 *
 * @param head
 * @return
 */
public ListNode swapPairs(ListNode head) {
    // If the list has no node or has only one node left.
    if ((head == null) || (head.next == null)) {
        return head;
    }
    // 虚拟充当链表头节点的prevNode，因此存储指向头节点的指针。
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev = dummy;
 
    while (head !=  null && head.next != null) {
        //待交换的两个指针
        ListNode first = head;
        ListNode second = head.next;
 
        // 交换
        prev.next = second;
        first.next = second.next;
        second.next = first;
 
        //跳跃，为下一轮的while循环进行全局变量的重新的“初始化”
        prev = first;
        head = first.next;
    }
    // 返回新的头结点
    return dummy.next;
}

参考资料：https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/liang-liang-jiao-huan-lian-biao-zhong-de-jie-di-19/

3、K 个一组翻转链表

问题描述：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

题解:

本题需要前面两个题目的知识铺垫，然后加以融合。一图胜千言，根据图片看代码，马上就懂了。

步骤分解:

1. 链表分区为已翻转部分+待翻转部分+未翻转部分
2. 每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
3. 需记录翻转链表前驱和后继，方便翻转完成后把已翻转部分和未翻转部分连接起来
4. 初始需要两个变量 pre 和 end，pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾
5. 经过k此循环，end 到达末尾，记录待翻转链表的后继 next = end.next
6. 翻转链表，然后将三部分链表连接起来，然后重置 pre 和 end 指针，然后进入下一次循环
7. 特殊情况，当翻转部分长度不足 k 时，在定位 end 完成后，end==null，已经到达末尾，说明题目已完成，直接返回即可
8. 时间复杂度为 $O(n * K)$最好的情况为 $O(n)$ 最差的情况未 $O(n^{2})$
9. 空间复杂度为 $O(1)$除了几个必须的节点指针外，我们并没有占用其他空间

代码实现：

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    //初始需要两个变量 pre 和 end, pre 代表待翻转链表的前驱，end 代表待翻转链表的末尾
    ListNode pre = dummy;
    ListNode end = dummy;
 
    while (end.next != null) {
        // 每次翻转前，要确定翻转链表的范围，这个必须通过 k 此循环来确定
        for (int i = 0; i < k && end != null; i++) end = end.next;
        // 剩余不满K个的不需要翻转了
        if (end == null) break;
 
        ListNode start = pre.next;
        ListNode next = end.next;
        // 断开链，才能让reverse函数进行翻转
        end.next = null;
        pre.next = reverse(start);
        start.next = next;
 
        // “重置”全局变量pre和end，便于下一轮循环
        pre = start;
        end = start;
    }
    return dummy.next;
}
 
// 这个是之前讲到的翻转链表的实现，代码是完全一样的
private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

参考资料：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/solution/tu-jie-kge-yi-zu-fan-zhuan-lian-biao-by-user7208t/

 做算法要多对比才能总结出套路来，然后照着模板一步一步的写出更高级的更难的算法出来。