LeetCode: 206 Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example:

Input: head = [1,2]
Output: [2,1]

Example:

Input: head = []
Output: []

问题

给定一个单链表的头节点，将链表反转，并返回反转后的链表。

解决方案 1

迭代法

Approach 1 / 方法 1

This solution uses an iterative approach to reverse the linked list. We maintain three pointers: prev, curr, and next. The idea is to reverse the direction of each link one by one until all nodes have been processed.

该解决方案使用迭代方法来反转链表。我们维护三个指针：prev、curr 和 next。其思想是逐个反转每个节点的指向，直到所有节点都被处理。

Implementation / 实现

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        return prev

Explanation / 解释

1. Initialize prev and curr / 初始化 prev 和 curr

   prev = None
   curr = head

   • English: We initialize prev to None and curr to the head of the list. prev will eventually become the new head of the reversed list, and curr is used to traverse the original list.
   • Chinese: 我们将 prev 初始化为 None，并将 curr 初始化为链表的头节点。prev 最终将成为反转后链表的新头节点，而 curr 用于遍历原链表。

2. Iterate Over the List / 遍历链表

   while curr:

   • English: We enter a loop that continues as long as curr is not None.
   • Chinese: 我们进入一个循环，只要 curr 不为 None，循环就会继续。

3. Store the Next Node / 存储下一个节点

   next_node = curr.next

   • English: We store the next node in next_node before we change the link. This is necessary because we will reverse the next pointer of the current node.
   • Chinese: 我们在改变链接之前，将下一个节点存储在 next_node 中。这是必要的，因为我们将反转当前节点的 next 指针。

4. Reverse the next Pointer / 反转 next 指针

   curr.next = prev

   • English: We reverse the next pointer of the current node to point to the previous node (prev).
   • Chinese: 我们将当前节点的 next 指针反转，使其指向前一个节点（prev）。

5. Move prev and curr One Step Forward / 将 prev 和 curr 向前移动一步

   prev = curr
   curr = next_node

   • English: We move the prev pointer to the current node (curr), and the curr pointer to the next node (next_node).
   • Chinese: 我们将 prev 指针移动到当前节点（curr），并将 curr 指针移动到下一个节点（next_node）。

6. Return the New Head of the Reversed List / 返回反转后链表的新头节点

   return prev

   • English: After the loop completes, prev will be pointing to the new head of the reversed list, so we return prev.
   • Chinese: 循环结束后，prev 将指向反转后链表的新头节点，因此我们返回 prev。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the linked list. We traverse each node exactly once.
• Space Complexity / 空间复杂度: O(1), as we are using only a constant amount of extra space for the pointers.

Key Concept / 关键概念

• Iterative Reversal / 迭代反转: The iterative approach is a simple and efficient way to reverse a linked list in-place, using only a few pointers.
• 迭代反转: 迭代方法是一种简单且高效的方式，用少量指针就能就地反转链表。

解决方案 2

递归法

Approach 2 / 方法 2

This solution uses recursion to reverse the linked list. The idea is to reverse the rest of the list after the first node and then place the first node at the end of the reversed list.

该解决方案使用递归来反转链表。其思想是反转第一个节点后的链表，然后将第一个节点放在反转链表的末尾。

Implementation / 实现

python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return new_head

Explanation / 解释

1. Base Case: Return the Last Node / 基本情况：返回最后一个节点

   if not head or not head.next:
      return head

   • English: If the current node is None or if it’s the last node in the list (head.next is None), we return it as the new head of the reversed list.
   • Chinese: 如果当前节点为 None 或它是链表的最后一个节点（head.next 为 None），我们将其作为反转链表的新头节点返回。

2. Recursive Step: Reverse the Rest of the List / 递归步骤：反转链表的其余部分

   new_head = self.reverseList(head.next)

   • English: We recursively call reverseList on the next node (head.next). This call will return the new head of the reversed list.
   • Chinese: 我们递归调用 reverseList，作用于下一个节点（head.next）。此调用将返回反转链表的新头节点。

3. Place the Current Node at the End / 将当前节点放在末尾

   head.next.next = head
   head.next = None

   • English: We set head.next.next to head to place the current node at the end of the reversed list. Then we set head.next to None to break the original link.
   • Chinese: 我们将 head.next.next 设置为 head，将当前节点放在反转链表的末尾。然后将 head.next 设置为 None，以断开原始链接。

4. Return the New Head / 返回新头节点

   return new_head

   • English: Finally, we return the new head of the reversed list.
   • Chinese: 最后，我们返回反转链表的新头节点。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the linked list. We traverse each node once.
• Space Complexity / 空间复杂度: O(n), due to the recursive call stack. In the worst case, the stack will hold n recursive calls.

Key Concept / 关键概念

• Recursive Reversal / 递归反转: The recursive approach is a more elegant way to reverse a linked list, though it requires more space due to the call stack.
• 递归反转: 递归方法是一种更优雅的反转链表的方式，但由于调用栈的存在，它需要更多的空间。

Comparison / 比较

1. Efficiency / 效率:

   • Iterative Approach / 迭代方法: More efficient in terms of space, with O(1) space complexity.
   • Recursive Approach / 递归方法: Easier to understand for some, but with O(n) space complexity due to

   recursion.

2. Use Case / 使用场景:

   • Iterative / 迭代: Preferred when memory usage is a concern.
   • Recursive / 递归: Preferred for its simplicity and elegance in code.

Summary / 总结

• English: Both the iterative and recursive approaches are valid for reversing a linked list. The iterative method is more space-efficient, while the recursive method is more elegant.
• Chinese: 迭代和递归方法都是反转链表的有效方法。迭代方法在空间上更高效，而递归方法在代码上更优雅。

Tips / 提示

• English: Choose the iterative approach for large lists to avoid stack overflow.
• Chinese: 对于大型链表，选择迭代方法以避免栈溢出。

Solution Template for Similar Questions / 提示

• English: Use the iterative approach for in-place modifications and the recursive approach for problems that naturally fit recursion.
• Chinese: 对于就地修改的场景，使用迭代方法；对于自然适合递归的问题，使用递归方法。

5 More Similar Questions / 推荐5问题

1. LeetCode 92. Reverse Linked List II
2. LeetCode 25. Reverse Nodes in k-Group
3. LeetCode 24. Swap Nodes in Pairs
4. LeetCode 234. Palindrome Linked List
5. LeetCode 143. Reorder List

Recommended Resources / 推荐资源

• English: Practice reversing linked lists with both iterative and recursive methods to strengthen your understanding.
• Chinese: 通过迭代和递归方法练习反转链表，以加深理解。

LeetCode #206: Reverse Linked List | SWE Interview by Algo Engine

Reverse Linked List – Iterative AND Recursive – Leetcode 206 – Python by NeetCode