LeetCode 链表刷题笔记

目录：LeetCode 索引

1 链表反转（LeetCode 206）

反转一个单链表：1->2->3->4->5->NULL → 5->4->3->2->1->NULL

知识点

单链表的操作、指针的操作。

迭代法

单链表无法回溯，因此需要暂存前驱节点和后继节点：当前节点指针调整方向后，原下一个节点的信息会丢失（链条断了），必须在调整指针前暂存下一个节点。

算法：

定义两个指针：previous（初始为 None）和 current（初始为 head）；
迭代开始，先暂存 tmpNext = current.next；
调整当前节点的 next 指针指向前驱节点：current.next = previous；
previous 指向当前节点、current 指向 tmpNext；
current 不为空就继续迭代；
迭代结束（current 为 None），返回 previous（反转后的新链表头）。

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # previous 初始为 None，这样无需单独判断 head 为空或仅一个节点
        previous = None
        current = head
        while(current != None):
            # 关键：先保存下一个节点，否则一旦 current.next 指向前一个
            # 节点，剩余链表就丢失（『链条』断了）
            tmpNext = current.next

            # 当前节点指针指向前一个节点
            current.next = previous

            # 同时移动：当前节点变成上一个节点，下个节点变为当前节点
            previous = current
            current = tmpNext

        # 反转后 previous 才是新链表的头部（current 跳出时为 None）
        return previous

递归法

递归深度 n，空间复杂度 O(n)（隐式栈空间），时间复杂度 O(n)。

思路：假设 reverseListRecursion(head) 已实现”传入链表头、返回逆序后的头”。把 head 拿出来，对剩余部分调用函数，head 放到新链表尾部即可。

算法：

当前节点为空或下一个节点为空，返回当前节点（递归结束）；
调用 reverseListRecursion(head.next) 反转 head 之外的链表，返回新头部 newHead；
将新链表尾节点（即原 head.next）的 next 指向 head；
将 head 的 next 置空；
返回 newHead。

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

        # head.next 作为剩余部分的头指针，newHead 是新链表的头部
        newHead = self.reverseList(head.next)
        # head.next 代表新链表的尾，将其 next 置为 head 即把 head 加到末尾
        head.next.next = head
        head.next = None
        return newHead

参考：LeetCode 206 题解

2 删除链表的倒数第 N 个节点（LeetCode 19）

给定链表 1->2->3->4->5 和 n = 2，删除倒数第二个节点后链表变为 1->2->3->5。题目保证 n 有效。

知识点

单链表元素删除、指针操作、链表遍历。

方法一：双指针（无哑节点）

需要将被删除节点的上一个节点初始化为 None，应对删除头节点的特殊情况。

算法：

head 为空则直接返回；
三个指针：first 和 needToBeDeleted 指向 head，second 指向 None；
first 先移动 n 个节点；
同时移动 first、needToBeDeleted 和 second（second 指向 needToBeDeleted 上一个），直到 first 指向 None；
若待删除节点是 head，则 head = head.next；否则 second.next = needToBeDeleted.next；
needToBeDeleted.next = None 与链表断开；
返回 head。

        
      
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        '''
        @note: 使用两个指针 first/needToBeDeleted，first 先向前移动 n 个节点，
        然后同时移动两个指针，当 first 指向 None 时，needToBeDeleted 指向的
        节点就是要删除的倒数第 n 个节点；由于无法回溯，还需暂存 needToBeDeleted
        的上一个节点 second，以便更改指针指向。
        '''
        if head == None:
            return

        first = head
        second = None      # second 初始为 None 关键：当删除 head 时它指向 None
        needToBeDeleted = head

        # first 先移动 n 个节点
        while (n):
            first = first.next
            n -= 1

        # 将 first 移动到最后一个节点的下一个节点 None
        while(first):
            first = first.next
            second = needToBeDeleted
            needToBeDeleted = needToBeDeleted.next

        # 当要删除的节点是头节点时，单独处理
        if needToBeDeleted == head:
            head = head.next
        else:
            second.next = needToBeDeleted.next

        needToBeDeleted.next = None
        return head

方法二：哑节点

哑节点让 head 也变成普通节点，无需特判。

算法：

first 指向 head；创建哑节点，next 指向 head；needToBeDeletedPrevious 指向哑节点；
first 先移动 n 个节点；
同时移动 first 和 needToBeDeletedPrevious，直到 first 为 None；
needToBeDeletedPrevious.next = needToBeDeletedPrevious.next.next；
返回哑节点的 next 作为新链表头。

        
      
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        first = head
        dummyNode = ListNode(0)
        dummyNode.next = head
        needToBeDeletedPrevious = dummyNode

        # first 先移动 n 个节点
        while (n):
            first = first.next
            n -= 1

        # 将 first 移动到最后一个节点的下一个节点 None
        # 此时 needToBeDeletedPrevious 将指向被删除节点的上个节点
        while(first):
            first = first.next
            needToBeDeletedPrevious = needToBeDeletedPrevious.next

        # 被删除节点的上个节点的指针直接指向下下个节点
        needToBeDeletedPrevious.next = needToBeDeletedPrevious.next.next

        # 哑节点的 next 始终指向链表的头节点
        return dummyNode.next

3 两数相加（LeetCode 2）

用两个逆序存储的链表表示两个非负整数，每个节点存一位，返回两数相加的和（同样逆序存储）。如 2->4->3（342）+ 5->6->4（465）= 7->0->8（807）。

算法（进位 + 双链表遍历）：

初始化哑节点和进位 carry=0；
两个链表都非空或 carry 不为 0 时循环：取两节点值（空则为 0）+ carry 求和；
当前位 = sum % 10，进位 = sum / 10；
移动 l1、l2 指针与当前节点；
返回哑节点的 next。

        
      
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        cur = dummy
        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            s = v1 + v2 + carry
            carry = s // 10
            cur.next = ListNode(s % 10)
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        return dummy.next

阅读 — · 全站 —