【2025-02-27】基础算法：反转链表

用户11029137

发布于 2025-02-28 08:55:52

6700

代码可运行

运行总次数：0

代码可运行

📝前言说明： ●本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，主要跟随B站博主灵茶山的视频进行学习，专栏中的每一篇文章对应B站博主灵茶山的一个视频 ●题目主要为B站视频内涉及的题目以及B站视频中提到的“课后作业”。 ●文章中的理解仅为个人理解。 ●文章中的截图来源于B站博主灵茶山，如有侵权请告知。

一，视频题目

1，206. 反转链表

思路：不断让节点的next指向前一个节点，注意：需要一个额外变量来实现保存当前节点的下一个节点（以免丢失）

# 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]:
        pre = None # 前一节点
        cur = head # 当前节点
        while cur: # 即cur不为空
            nxt = cur.next # 记录当前节点的下一节点
            cur.next = pre # 让当前节点指向前一节点
            pre = cur # 修改完成后，当前节点变成前一节点
            cur = nxt # 下一个要操作的节点
        return pre # 返回反转后的链表头结点

注意：反转结束后，从原来的链表上看：pre指向反转这一段的末尾；cur指向反转这一段后续的下一个节点

2，92. 反转链表 II

按第1题的方法反转后：

要返回正确的答案，只需先让2指向5（cur）,再让1指向4（pre）特殊情况，如果left==1，则没有p0，所以可以添加一个哨兵节点，简化边界条件处理

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        p0 = dummy
        for _ in range(left-1):
            p0 = p0.next # 共移动left-1次,停在要反转的前一个位置
        pre = None
        cur = p0.next
        for _ in range(right-left+1):  # 共需要操作right-left+1个元素
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        p0.next.next = cur
        p0.next = pre
        return dummy.next

3，25. K 个一组翻转链表

和第92题类似，关键在于要不断更新哨兵节点的位置，新哨兵节点的位置应该为上一次反转链表后的末尾，即：p0.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        n = 0
        cur = head
        while cur: # 统计链表长度
            n += 1
            cur = cur.next
        t = n // k # 需要反转的组数
        dummy = ListNode(next = head)
        p0 = dummy
        for _ in range(t):
            pre = None
            cur = p0.next
            for _ in range(k):
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            nxt_p0 = p0.next
            p0.next.next = cur
            p0.next = pre
            p0 = nxt_p0
        return dummy.next

二，课后作业

1，24. 两两交换链表中的节点

规定一下交换顺序

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node0 = dummy = ListNode(next = head)
        node1 = head
        while node1 and node1.next: # 至少有两个节点
            node2 = node1.next
            node3 = node2.next

            node0.next = node2 # 0 -> 2
            node2.next = node1 # 2 -> 1
            node1.next = node3 # 1 -> 3

            node0 = node1 # 交换完的末尾是下一次的哨兵
            node1 = node3
        return dummy.next

2，445. 两数相加 II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reserve_list(self, head):
        pre = None
        cur = head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre
    def addTwo(self,l1,l2):
        cur = dummy = ListNode()
        carry = 0 # 进位
        while l1 or l2 or carry: # 因为这里是or，所以循环内部要分别判断
            if l1: carry += l1.val # 这里用carry直接作为和，因为后续通过对carry的直接操作可以得到进位
            if l2: carry += l2.val
            cur.next = ListNode(val = carry % 10)
            carry //= 10
            cur = cur.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return dummy.next
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # 反转链表+两数相加
        l1 = self.reserve_list(l1)
        l2 = self.reserve_list(l2)
        l3 = self.addTwo(l1, l2)
        return self.reserve_list(l3)

3，2816. 翻倍以链表形式表示的数字

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 方法一：看成是两个List相加
        # 方法二：考虑到额外的进位，提前增加一个节点；如果有进位，即当前的数字 > 4
        if head.val > 4:
            head = ListNode(0, head)
        cur = head
        while cur:
            cur.val = cur.val * 2 % 10
            if cur.next and cur.next.val > 4:
                cur.val += 1
            cur = cur.next
        return head

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-27，如有侵权请联系 cloudcommunity@tencent.com 删除

视频