该系列题目取自 LeetCode 精选 TOP 面试题列表:https://leetcode-cn.com/problemset/top/
LeetCode 206. 反转链表:https://leetcode-cn.com/problems/reverse-linked-list/
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
在上一篇《图解精选 TOP 面试题 005 | 反转链表之迭代求解》中,我们介绍了该题的迭代求解法,本篇再说说如何进行递归求解。
首先,在写代码前,我们需要先进行「递归设计」,即明确三点:
递归函数的作用为:改变当前节点下一个节点的 next
指针,使其指向当前节点。
听起来有点拗口,用代码表示就是这样的:
# 当前节点的下一个节点
next_node = head.next
# 改变下一个节点的指针
next_node.next = head
我们用这样的方式就完成了某两个节点之间指向的反转。
除此之外,为了防止链表循环,我们还要切断当前节点的 next
指向,即设 head.next
为空。
当节点为空或节点的 next
节点为空时,返回当前节点。
这样的结束条件我们可以理解为:空节点或只有一个节点时,它的反转就是其本身。
在迭代法中,我们为了反转与遍历,不断地保存上一个节点与下一个节点,整个过程显得小心翼翼。而在递归中,我们先根据链表原有的顺序利用递归将节点依次入栈,之后再层层弹出,从而反转节点之间的指向。
因此,在节点不为空且节点的下一个节点不为空时,我们进行递归调用,以此不断地将当前节点的下一个节点压入栈区,直至链表尾部。
以题目中的 1->2->3->4->5->NULL
为例,整个反转过程如下:
反转过程
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
# 不断往后获取节点
cur = self.reverseList(head.next)
# 反转节点指向
next_node = head.next
next_node.next = head
# 切断当前节点的 next 指向
head.next = None
return cur
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
cur := reverseList(head.Next)
nextNode := head.Next
nextNode.Next = head
head.Next = nil
return cur
}