devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2024.6.7力扣刷题记录-链表篇学习记录

作者：知新_RL | 2024-06-17 00:25:48

赞

踩

2024.6.7力扣刷题记录-链表篇学习记录

目录

一、学习视频

二、视频跟练

1.206. 反转链表

2.92. 反转链表 II

3.25. K 个一组翻转链表

三、课后习题

1.24. 两两交换链表中的节点

（1）循环两次

 （2）直接反转

（3）递归

2.445. 两数相加 II

（1）迭代-原地修改-错误

（2）迭代-开新链表

（3）递归

 （4）栈

3.2816. 翻倍以链表形式表示的数字

（1）栈-原地-三次遍历

（2）栈-新建链表-两次遍历

（3）反转链表-原地修改-两次遍历

（4）一次遍历

（5）一次遍历2

一、学习视频

【反转链表】 https://www.bilibili.com/video/BV1sd4y1x7KN/?share_source=copy_web&vd_source=dc0e55cfae3b304619670a78444fd795

二、视频跟练

1.206. 反转链表

来自视频

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         pre = None
  9.         cur = head
  10.         while cur:
  11.             nxt = cur.next
  12.             cur.next = pre
  13.             pre = cur
  14.             cur = nxt 
  15.         return pre

2.92. 反转链表 II

来自视频

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
  8.         dummy = ListNode(next = head)   # 哨兵节点
  9.         p0 = dummy
  10.         # 到达反转开始位置
  11.         for _ in range(left - 1):
  12.             p0 = p0.next
  13.         
  14.         # 开始反转
  15.         pre, cur = None, p0.next
  16.         for _ in range(right - left + 1):
  17.             nxt = cur.next
  18.             cur.next = pre
  19.             pre = cur
  20.             cur = nxt
  21.         
  22.         # 连接
  23.         p0.next.next = cur
  24.         p0.next = pre
  25.         return dummy.next

3.25. K 个一组翻转链表

来自视频

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
  8.         # 获取链表长度
  9.         n = 0
  10.         cur = head
  11.         while cur:
  12.             n += 1
  13.             cur = cur.next
  14.  
  15.         dummy = ListNode(next = head)   # 哨兵节点
  16.         pre = None
  17.         cur = head
  18.         p0 = dummy
  19.         while n >= k:
  20.             n -= k
  21.             for _ in range(k):
  22.                 nxt = cur.next 
  23.                 cur.next = pre
  24.                 pre = cur
  25.                 cur = nxt
  26.  
  27.             nxt = p0.next   # 这里是关键，p0.next是旋转后的cur的前一位
  28.             p0.next.next = cur
  29.             p0.next = pre
  30.             p0 = nxt
  31.             # pre = nxt   # 这里对pre进行更新
  32.             '''
  33.             这里为什么可以不用更新pre，
  34.             当未更新时，cur指向pre时，cur是p0的下一个节点
  35.             当进行拼接时，p0.next.next = cur，会改变当时cur的那一条指向
  36.             所有更不更新没有关系
  37.             '''
  38.         return dummy.next

三、课后习题

1.24. 两两交换链表中的节点

（1）循环两次

k个节点循环的做法，此时k=2。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         dummy = ListNode(next = head)
  9.         p0 = dummy     # p0和dummy最开始指向同一个节点
  10.         cur = head
  11.         pre = None
  12.         while cur and cur.next:
  13.             for _ in range(2):
  14.                 nxt = cur.next
  15.                 cur.next = pre
  16.                 pre = cur
  17.                 cur = nxt
  18.  
  19.             nxt = p0.next
  20.             p0.next.next = cur
  21.             p0.next = pre
  22.             p0 = nxt
  23.         return dummy.next

 （2）直接反转

两个为一组直接进行反转连接

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 直接交换
  9.         dummy = ListNode(next = head)
  10.         p0 = dummy
  11.         pre = head
  12.         while pre and pre.next:
  13.             cur = pre.next
  14.             nxt = cur.next
  15.  
  16.             p0.next = cur
  17.             cur.next = pre
  18.             pre.next = nxt
  19.             
  20.             p0 = pre
  21.             pre = nxt
  22.         return dummy.next

（3）递归

来自官方题解（. - 力扣（LeetCode））。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 递归
  9.         if not head or not head.next:
  10.             return head
  11.         newhead = head.next     # 第二个节点p2
  12.         # 将后面的节点（第二个后的）进行反转，反转后返回的部分连接在第一个节点p1的后面
  13.         head.next = self.swapPairs(newhead.next)
  14.         newhead.next = head     #p2后面接p1，反转
  15.         return newhead

2.445. 两数相加 II

（1）迭代-原地修改-错误

当l1，l2遍历完但有进位时，会缺少节点，最好还是使用开新的储存空间的方法。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 迭代
  9.         def transform(head: Optional[ListNode]) -> Optional[ListNode]:
  10.             pre = None
  11.             cur = head
  12.             while cur:
  13.                 nxt = cur.next
  14.                 cur.next = pre
  15.                 pre = cur
  16.                 cur = nxt
  17.             return pre
  18.  
  19.         l1 = transform(l1)
  20.         l2 = transform(l2)
  21.         pre1 = None
  22.         cur1, cur2 = l1, l2
  23.         # 假定l1长，将所有运算结果储存在l1上
  24.         num = 0
  25.         while cur1 and cur2:
  26.             # 数字操作
  27.             x = cur1.val + cur2.val + num
  28.             num = x // 10
  29.             cur1.val = x % 10
  30.  
  31.             # 反转操作
  32.             nxt = cur1.next
  33.             cur1.next = pre1
  34.             pre1 = cur1
  35.             cur1 = nxt
  36.  
  37.             # 迭代
  38.             cur2 = cur2.next
  39.         if not cur1:
  40.             cur1 = cur2
  41.         while cur1:
  42.             # 数字操作
  43.             x = cur1.val + num
  44.             num = x // 10
  45.             cur1.val = x % 10
  46.  
  47.             # 反转操作
  48.             nxt = cur1.next
  49.             cur1.next = pre1
  50.             pre1 = cur1
  51.             cur1 = nxt
  52.         return pre1

（2）迭代-开新链表

来自灵神题解（. - 力扣（LeetCode））。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.             pre = None
  9.             cur = head
  10.             while cur:
  11.                 nxt = cur.next
  12.                 cur.next = pre
  13.                 pre = cur
  14.                 cur = nxt
  15.             return pre
  16.  
  17.     def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  18.         cur = dummy = ListNode()
  19.         carry = 0   # 进位
  20.         while l1 or l2 or carry:
  21.             if l1: carry += l1.val
  22.             if l2: carry += l2.val
  23.             cur.next = ListNode(carry % 10)
  24.             cur = cur.next
  25.             carry //= 10    # 注意更新
  26.             if l1: l1 = l1.next
  27.             if l2: l2 = l2.next
  28.         return dummy.next
  29.  
  30.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  31.         # 迭代-开新链表
  32.         l1 = self.reverseList(l1)
  33.         l2 = self.reverseList(l2)
  34.         newList = self.addTwo(l1, l2)
  35.         return self.reverseList(newList)

（3）递归

来自灵神题解。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         if not head or not head.next:
  9.             return head
  10.         newhead = self.reverseList(head.next)   # 此时的头节点为原来链表的最后一个节点
  11.         # 反转操作，此时相当于是对尾操作，与头节点无关
  12.         head.next.next = head
  13.         head.next = None    # 尾节点
  14.         return newhead
  15.  
  16.     def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry = 0) -> Optional[ListNode]:
  17.         if not l1 and not l2:
  18.             return ListNode(carry) if carry else None
  19.         if not l1:
  20.             l1, l2 = l2, l1     # 保证l1是非空的，便于返回
  21.         carry += l1.val + (l2.val if l2 else 0)
  22.         l1.val = carry % 10
  23.         l1.next = self.addTwo(l1.next, l2.next if l2 else None, carry // 10)
  24.         return l1
  25.  
  26.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  27.         # 递归
  28.         l1 = self.reverseList(l1)
  29.         l2 = self.reverseList(l2)
  30.         newList = self.addTwo(l1, l2)
  31.         return self.reverseList(newList)

 （4）栈

来自官方题解（. - 力扣（LeetCode））。

先全部入栈，弹出一个运算一次头插一次。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 栈，运算顺序，后进先出
  9.         s1, s2 = [], []
  10.         # 全部入栈
  11.         while l1:
  12.             s1.append(l1.val)
  13.             l1 = l1.next
  14.         while l2:
  15.             s2.append(l2.val)
  16.             l2 = l2.next
  17.         dummy = ListNode()
  18.         carry = 0
  19.         while s1 or s2 or carry:
  20.             s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
  21.             carry, val = divmod(s, 10)
  22.             dummy.next = ListNode(val, dummy.next)      # 头插法
  23.         return dummy.next

3.2816. 翻倍以链表形式表示的数字

（1）栈-原地-三次遍历

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 栈-原地-三次遍历
  9.         # 逆序运算可以使用栈
  10.         start, end = [], []     # 运算，更新均使用栈
  11.         cur = head
  12.         # 入栈
  13.         while cur:
  14.             start.append(cur.val)
  15.             cur = cur.next
  16.         # 运算
  17.         carry = 0
  18.         while start:
  19.             carry += start.pop() * 2
  20.             end.append(carry % 10)
  21.             carry //= 10
  22.         # 更新答案
  23.         dummy = ListNode(val = carry if carry else 0, next = head)
  24.         cur = head
  25.         while cur:
  26.             cur.val = end.pop()
  27.             cur = cur.next
  28.         return dummy if dummy.val else dummy.next

（2）栈-新建链表-两次遍历

又用到了栈，又用到了头插法，又新建节点，效率不是很高。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 栈-新建链表-两次遍历
  9.         start = []
  10.         cur = head
  11.         # 入栈
  12.         while cur:
  13.             start.append(cur.val)
  14.             cur = cur.next
  15.         # 运算
  16.         carry = 0
  17.         dummy = ListNode()
  18.         while start:
  19.             carry += start.pop() * 2
  20.             dummy.next = ListNode(val = carry % 10, next = dummy.next)
  21.             carry //= 10
  22.         if carry: dummy.next = ListNode(val = carry, next = dummy.next)
  23.         return dummy.next

（3）反转链表-原地修改-两次遍历

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 反转链表-原地修改-两次遍历
  9.         # 反转链表
  10.         cur = head
  11.         pre = None
  12.         while cur:
  13.             nxt = cur.next
  14.             cur.next = pre
  15.             pre = cur
  16.             cur = nxt
  17.         
  18.         carry = 0
  19.         cur = pre
  20.         pre = None
  21.         while cur:
  22.             # 运算
  23.             carry += cur.val * 2
  24.             cur.val = carry % 10
  25.             carry //= 10
  26.             # 反转
  27.             nxt = cur.next
  28.             cur.next = pre
  29.             pre = cur
  30.             cur = nxt
  31.         dummy = ListNode(next = pre)
  32.         if carry: dummy.next = ListNode(val = carry, next = dummy.next)
  33.         return dummy.next

（4）一次遍历

来自灵神题解（. - 力扣（LeetCode））。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 一次遍历
  9.         # 总结规律
  10.         if head.val > 4:
  11.             # 添加一位
  12.             head = ListNode(0, head)
  13.         cur = head
  14.         while cur:
  15.             cur.val = cur.val * 2 % 10
  16.             if cur.next and cur.next.val > 4:
  17.                 cur.val += 1
  18.             cur = cur.next
  19.         return head

（5）一次遍历2

来自题解（. - 力扣（LeetCode））。和（4）的解法道理是一样的，都是根据数值的范围确定只能进位一次。（4）是从上节点的角度，而（5）是从下节点的角度。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         # 一次遍历2
  9.         dummy = ListNode(next = head)
  10.         pre = dummy
  11.         cur = head
  12.         while cur:
  13.             newVal = cur.val * 2
  14.             pre.val += newVal // 10
  15.             cur.val = newVal % 10
  16.  
  17.             pre = cur
  18.             cur = cur.next
  19.         return dummy if dummy.val else dummy.next

完

感谢你看到这里！一起加油吧！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/728876
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号