字节一面：链表反转的姿势，你知道几个？

布满荆棘的人生 2022-10-24 01:48 14阅读 0赞

![format_png][]

今天分享的内容就是关于如何用递归思想来反转链表的，分享的题目是：

*  LeetCode \#206 反转链表
 *  LeetCode \#92 反转链表||

友情提示：**在用递归思想解题时，明确递推公式的含义后，不要试图想明白每一步是如何递归的**，这很容易把自己绕晕哈。

**01**

**LeetCode \#206 反转链表**

**题目描述：**

反转一个单链表。

**示例:**

**输入:** 1->2->3->4->5->NULL

**输出:** 5->4->3->2->1->NULL

**思路分析：**

示例给出的链表，如下图所示：

![format_png 1][]

递归解题首先要做的是**明确递推公式的含义**，在这里对于head指向结点1来说，它只需要知道它之后的所有节点反转之后的结果就可以了，也就是说递推公式reverseList的含义是：把拿到的链表进行反转，然后返回新的头结点。

![format_png 2][]

结点1之后的结点，经过递归公式reverseList处理之后的结果如下图：

![format_png 3][]

到这里，就可以写出如下的代码了。

public ListNode reverseList(ListNode head) {
        // 调用递推公式反转当前结点之后的所有节点
        // 返回的结果是反转后的链表的头结点
        ListNode newHead = reverseList(head.next);
    }

接着要做的就是反转head指向的结点1，也就是将head指向的结点作为其下一个结点的下一个结点，即head.next.next=head。

![format_png 4][]

最后，将head指向的结点的下一个结点置为null，就完成了整个链表的反转。

![format_png 5][]

将反转head指向的结点的代码完善之后，就可以得到如下的代码：

public ListNode reverseList(ListNode head) {
        // 调用递推公式反转当前结点之后的所有节点
        // 返回的结果是反转后的链表的头结点
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

递归调用这一部分完成之后，还有重要的一步就是**递归终止条件，**递归反转链表什么时候停止呢？在head指向的结点为null或head指向的结点的下一个结点为null时停止，因为在这两种情况下，反转后的结果就是它自己。到这里，就可以写出完整的代码了：

public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
    
    
        // 调用递推公式反转当前结点之后的所有节点
        // 返回的结果是反转后的链表的头结点
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

**02**

**LeetCode \#92 反转链表||**

**题目描述：**

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:  
1 ≤ m ≤ n ≤ 链表长度。

**示例:**

输入: 1->2->3->4->5->NULL, m = 2, n = 4
    输出: 1->4->3->2->5->NULL

**思路分析：**

为了方便说明一个问题，这里以链表1->2->3->4->5->6->NULL, m = 3, n = 5为例进行分析如何用递归思想求解该题目。

![format_png 6][]

在这里head指向的结点1，不用关注其后的所有结点时如何将m=3与n=5之间的部分反转的，它只需要知道反转后的结果就可以。也就是说，在这里递推公式reverseBetween的含义是：将拿到的链表反转，然后返回反转后的链表的头结点。

![format_png 7][]

这样就可以初步写出如下的代码：

public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode between = reverseBetween(head.next, m-1,n-1);
    }

接着要做的就是，将递推公式reverseBetween返回的结果，挂在head之后，即head.next=between。

![format_png 8][]

这时，代码可以进一步完善，如下所示：

public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode between = reverseBetween(head.next, m-1,n-1);
        head.next = between;
        return head;
    }

递推公式的部分已经完成了，接着要明确的就是递归终止条件。在这里原问题是反转链表：1->2->3->4->5->6->NULL, m = 3, n = 5之间的部分。

更小的子问题是反转链表：2->3->4->5->6->NULL, m = 2, n = 4之间的部分。

在进一步是反转链表：3->4->5->6->NULL, m = 1, n = 3之间的部分。但是，这时这个子问题和上一个子问题还是可以用相同思路求解的同一个子问题吗？

![format_png 9][]

不是。

原因在于对于子问题：2->3->4->5->6->NULL, m = 2, n = 4来说，它只需要将其之后的所有结点反转之后的结点挂在自己之后就可以了。但是，对于问题3->4->5->6->NULL, m = 1, n = 3来说，结点3本身也是需要反转的。

对于如何用递归思想反转3->4->5->6->NULL, m = 1, n = 3一会儿再说。到这里，递归终止条件就明了了，即m=1时停止，代码如下：

public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return 待补充;
        }
    
    
        ListNode between = reverseBetween(head.next, m-1,n-1);
        head.next = between;
        return head;
    }

说明：以下部分是借鉴的labuladong大佬新作《labuladong的算法小抄》一书中的相关内容。

接着我们看下如何用递归思想反转3->4->5->6->NULL, m = 1, n = 3，即如何反转链表的前n个结点。

![format_png 10][]

这里，递推公式reverseTopN的含义是反转链表的前n个结点并返回被反转的链表的头结点。因此，其需要的参数有两个，一是待反转的链表的头结点，二是反转前几个结点，即n。

![format_png 11][]

对于链表4->5->6->NULL, n = 2来说，经过递推公式reverseTopN处理之后，结果如下图所示：

![format_png 12][]

至此，对于反转链表的前n个结点，可以初步写出如下的代码：

private ListNode reverseTopN(ListNode head, int n) {
        ListNode newHead = reverseTopN(head.next, n-1);
    }

经过前面分析，我们知道head指向的结点3也是需要反转的，即head.next.next=head。但是，我们发现在完成这一步操作后，结点6没法在和其它结点产生联系了。

![format_png 13][]

这个问题怎么解决呢？我们可以用topNSuccessor这个变量，指向第n个结点之后的结点。

![format_png 14][]

这时，在反转结点3，即head.next.next=head之后，我们可以将topNSuccessor指向的结点挂在head指向的结点之后，即head.next=topNSuccessor。

![format_png 15][]

head.next.next=head

![format_png 16][]

head.next=topNSuccessor

这时，反转链表前N个结点的代码进一步完善如下：

private ListNode reverseTopN(ListNode head, int n) {
        ListNode newHead = reverseTopN(head.next, n-1);
        head.next.next = head;
        head.next = topNSuccessor;
        return newHead;
    }

这时就有一个问题，topNSuccessor怎么确定的呢？

我们先看下反转链表前n个结点的递归终止条件是什么。当只需要反转链表的第一个结点时，返回原链表就可以了，即反转链表前n个结点的递归终止条件是n==1。

如下图，当n==1时，我们就可以确定topNSuccessor是head指向的结点的下一个结点。

![format_png 17][]

到这里反转链表的前n个结点的代码就可以完善了，具体代码如下：

ListNode topNSuccessor = null;
    
    
    private ListNode reverseTopN(ListNode head, int n) {
        if (n == 1) {
            topNSuccessor = head.next;
            return head;
        }
    
    
        ListNode newHead = reverseTopN(head.next, n-1);
        head.next.next = head;
        head.next = topNSuccessor;
        return newHead;
    }

最后，反转从位置 m 到 n 的链表的递归实现完整代码如下：

public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return reverseTopN(head, n);
        }
    
    
        ListNode between = reverseBetween(head.next, m-1,n-1);
        head.next = between;
        return head;
    }
    
    
    ListNode topNSuccessor = null;
    
    
    private ListNode reverseTopN(ListNode head, int n) {
        if (n == 1) {
            topNSuccessor = head.next;
            return head;
        }
    
    
        ListNode newHead = reverseTopN(head.next, n-1);
        head.next.next = head;
        head.next = topNSuccessor;
        return newHead;
    }

![format_png 18][]

[format_png]: /images/20221024/ae62b65be12b42adbe492ffc7fdb08af.png
[format_png 1]: /images/20221024/baa76c5272a44df2a50bd1668e836f02.png
[format_png 2]: /images/20221024/fc307f58521f44618261c76617b4bd40.png
[format_png 3]: /images/20221024/0d9d46db014c4196bbbcb4342137356c.png
[format_png 4]: /images/20221024/e6e9aa847b434dbfa6d09f2fe42a5f36.png
[format_png 5]: /images/20221024/e10657e0566a442a93a0805f79302a00.png
[format_png 6]: /images/20221024/4a9d33d4118a4014bf4e7953e2b0fd48.png
[format_png 7]: /images/20221024/8810ae36bebf463491ce37cd9d55cbb4.png
[format_png 8]: /images/20221024/4a0c9e57344141108b2df102fdddbe6b.png
[format_png 9]: /images/20221024/1e7f6e0dc944444393cb8355d06ccfa3.png
[format_png 10]: /images/20221024/739b19eeea1243529d2e16d5c47264c0.png
[format_png 11]: /images/20221024/0fe9bed816814a0b951701c3efbda334.png
[format_png 12]: /images/20221024/2df3cfadc23f4f69a168a12c2719615f.png
[format_png 13]: /images/20221024/669131eec3ad4d98ab7b81c6445078c3.png
[format_png 14]: /images/20221024/3ce86f173c5a455aaf8c7de23f8fe5c9.png
[format_png 15]: /images/20221024/518d3955a78649cca9fcb3d610622a46.png
[format_png 16]: /images/20221024/254e7a427f944a17b786eb393e3f849d.png
[format_png 17]: /images/20221024/44434c93ca304c59915ea43bc9684d76.png
[format_png 18]: /images/20221024/1eaf713066d6499faf0e4fe9a26ca94a.png