LeetCode Algorithm 206. 反转链表
本文将详细介绍 LeetCode 中的算法题目 206. 反转链表。我们将探讨问题的背景和要求，并提供一种解决方案和相应的代码实现。
1. 问题背景和要求
在链表问题中，反转链表是一个常见的操作。给定一个单链表的头节点 head，我们需要将链表反转，使得原先位于链表尾部的节点现在变为新链表的头节点。
以下是问题的具体要求：
1.1 输入
单链表的头节点 head。
1.2 输出
反转后的链表的头节点。
2. 解决方案
我们可以使用迭代和递归两种方法来解决这个问题。
2.1 迭代法
迭代法是最直观的解决方案。我们可以定义三个指针 prev、curr 和 next。
初始时，prev 指向 None，curr 指向 head。然后，我们使用一个循环来遍历链表，每次迭代时，将 curr 的 next 指针指向 prev，然后将 prev 和 curr 向后移动一个节点。这样，当循环结束时，prev 就指向了原链表的尾节点，将 prev 设为新的头节点，并返回 prev。
下面是迭代法的代码实现：
def reverseList(head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
这段代码遍历了整个链表，时间复杂度为 O(n)，其中 n 是链表的长度。
2.2 递归法
递归法是另一种解决问题的方法，对于链表问题，递归法通常更加简洁清晰。我们可以定义一个递归函数 reverse，它接受一个节点 head 作为参数。
递归函数的终止条件是当 head 为空（即链表为空）或者 head.next 为空时，直接返回 head。
然后，我们调用递归函数 reverse，传入 head.next，并将返回的结果记为 newHead。接下来，我们让 head 的 next 节点的 next 指针指向 head，然后将 head 的 next 指针指向 None。最后，返回 newHead，即反转后的链表的头节点。
下面是递归法的代码实现：
def reverseList(head):
if not head or not head.next:
return head
newHead = reverseList(head.next)
head.next.next = head
head.next = None
return newHead
3. 总结
本文详细介绍了 LeetCode 中的算法题目 206. 反转链表。我们分别讨论了迭代法和递归法两种解决方案，并给出了相应的代码实现。
对于迭代法，我们使用三个指针 prev、curr 和 next，分别表示反转后的链表的前一个节点、当前节点和下一个节点。通过循环迭代，将当前节点的 next 指针指向前一个节点，然后将前一个节点和当前节点向后移动一个节点，最终得到反转后的链表。
对于递归法，我们定义了一个递归函数 reverse，将 head 作为参数。递归函数的终止条件是当 head 为空或者 head 的下一个节点为空时，直接返回 head。然后，我们调用递归函数 reverse，传入 head.next，并将返回的结果记为 newHead。接着，我们将 head 的 next 节点的 next 指针指向 head，并将 head 的 next 指针指向 None。最后，返回 newHead，即反转后的链表的头节点。
通过以上两种方法，我们可以有效地解决反转链表的问题。
关键代码
迭代法：
def reverseList(head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
return prev
递归法：
def reverseList(head):
if not head or not head.next:
return head
newHead = reverseList(head.next)
head.next.next = head
head.next = None
return newHead
希望本文对理解并解决 LeetCode 中的算法题目 206. 反转链表有所帮助。