反转链表

本文介绍了反转链表的两种解法：使用字典存储前驱节点的笨办法，以及使用双指针迭代的高效方法，并附有详细代码和边界说明。

Leetcode 链表 Python

阅读要点

反转链表是链表操作的基础题。
解法一使用字典存储前驱节点，空间复杂度 O(n)。
解法二使用双指针原地反转，空间复杂度 O(1)。
注意处理空链表和单节点边界。
反转后需将原头节点的 next 置为 None 避免成环。

题目

206. 反转链表 - 力扣（LeetCode）

解法一：字典法

思路：先遍历链表，用字典记录每个节点的前驱节点。然后从尾节点开始，利用字典反向连接，最后将原头节点的 next 置为 None 避免成环。

复杂度：时间复杂度 O(n)，空间复杂度 O(n)。

答案

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 处理空链或单节点
        if not head or not head.next:
            return head 
        mp = collections.defaultdict()
        temp = head
        while(temp.next):
            mp[temp.next] = temp
            temp = temp.next
        res = temp
        while temp in mp:
            temp.next = mp[temp]
            temp = temp.next
        temp.next = None  # 不加则成环了，提交会超时
        return res

解法二：双指针法

思路：使用 pre 和 cur 两个指针，pre 初始为 None，cur 指向头节点。遍历链表，每次将 cur.next 指向 pre，然后 pre 和 cur 同时前进。注意在修改 cur.next 前需要暂存下一个节点。

复杂度：时间复杂度 O(n)，空间复杂度 O(1)。

答案

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        pre = None
        cur = head
        while cur.next:
            temp = cur.next
            cur.next = pre
            pre = cur
            cur = temp
        cur.next = pre
        return  cur