目录
一、学习视频
【反转链表】 https://www.bilibili.com/video/BV1sd4y1x7KN/?share_source=copy_web&vd_source=dc0e55cfae3b304619670a78444fd795
二、视频跟练
1.206. 反转链表
来自视频
# 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:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre2.92. 反转链表 II
来自视频
# 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
# 开始反转
pre, cur = None, p0.next
for _ in range(right - left + 1):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
# 连接
p0.next.next = cur
p0.next = pre
return dummy.next3.25. K 个一组翻转链表
来自视频
# 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
dummy = ListNode(next = head) # 哨兵节点
pre = None
cur = head
p0 = dummy
while n >= k:
n -= k
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
nxt = p0.next # 这里是关键，p0.next是旋转后的cur的前一位
p0.next.next = cur
p0.next = pre
p0 = nxt
# pre = nxt # 这里对pre进行更新
'''
这里为什么可以不用更新pre，
当未更新时，cur指向pre时，cur是p0的下一个节点
当进行拼接时，p0.next.next = cur，会改变当时cur的那一条指向
所有更不更新没有关系
'''
return dummy.next三、课后习题
1.24. 两两交换链表中的节点
（1）循环两次
k个节点循环的做法，此时k=2。
# 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]:
dummy = ListNode(next = head)
p0 = dummy # p0和dummy最开始指向同一个节点
cur = head
pre = None
while cur and cur.next:
for _ in range(2):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
nxt = p0.next
p0.next.next = cur
p0.next = pre
p0 = nxt
return dummy.next（2）直接反转
两个为一组直接进行反转连接
# 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]:
# 直接交换
dummy = ListNode(next = head)
p0 = dummy
pre = head
while pre and pre.next:
cur = pre.next
nxt = cur.next
p0.next = cur
cur.next = pre
pre.next = nxt
p0 = pre
pre = nxt
return dummy.next（3）递归
来自官方题解（. - 力扣（LeetCode））。
# 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]:
# 递归
if not head or not head.next:
return head
newhead = head.next # 第二个节点p2
# 将后面的节点（第二个后的）进行反转，反转后返回的部分连接在第一个节点p1的后面
head.next = self.swapPairs(newhead.next)
newhead.next = head #p2后面接p1，反转
return newhead2.445. 两数相加 II
（1）迭代-原地修改-错误
当l1，l2遍历完但有进位时，会缺少节点，最好还是使用开新的储存空间的方法。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 迭代
def transform(head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
l1 = transform(l1)
l2 = transform(l2)
pre1 = None
cur1, cur2 = l1, l2
# 假定l1长，将所有运算结果储存在l1上
num = 0
while cur1 and cur2:
# 数字操作
x = cur1.val + cur2.val + num
num = x // 10
cur1.val = x % 10
# 反转操作
nxt = cur1.next
cur1.next = pre1
pre1 = cur1
cur1 = nxt
# 迭代
cur2 = cur2.next
if not cur1:
cur1 = cur2
while cur1:
# 数字操作
x = cur1.val + num
num = x // 10
cur1.val = x % 10
# 反转操作
nxt = cur1.next
cur1.next = pre1
pre1 = cur1
cur1 = nxt
return pre1（2）迭代-开新链表
来自灵神题解（. - 力扣（LeetCode））。
# 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:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode()
carry = 0 # 进位
while l1 or l2 or carry:
if l1: carry += l1.val
if l2: carry += l2.val
cur.next = ListNode(carry % 10)
cur = cur.next
carry //= 10 # 注意更新
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.reverseList(l1)
l2 = self.reverseList(l2)
newList = self.addTwo(l1, l2)
return self.reverseList(newList)（3）递归
来自灵神题解。
# 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
newhead = self.reverseList(head.next) # 此时的头节点为原来链表的最后一个节点
# 反转操作，此时相当于是对尾操作，与头节点无关
head.next.next = head
head.next = None # 尾节点
return newhead
def addTwo(self, l1: Optional[ListNode], l2: Optional[ListNode], carry = 0) -> Optional[ListNode]:
if not l1 and not l2:
return ListNode(carry) if carry else None
if not l1:
l1, l2 = l2, l1 # 保证l1是非空的，便于返回
carry += l1.val + (l2.val if l2 else 0)
l1.val = carry % 10
l1.next = self.addTwo(l1.next, l2.next if l2 else None, carry // 10)
return l1
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 递归
l1 = self.reverseList(l1)
l2 = self.reverseList(l2)
newList = self.addTwo(l1, l2)
return self.reverseList(newList)（4）栈
来自官方题解（. - 力扣（LeetCode））。
先全部入栈，弹出一个运算一次头插一次。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 栈，运算顺序，后进先出
s1, s2 = [], []
# 全部入栈
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
dummy = ListNode()
carry = 0
while s1 or s2 or carry:
s = (0 if not s1 else s1.pop()) + (0 if not s2 else s2.pop()) + carry
carry, val = divmod(s, 10)
dummy.next = ListNode(val, dummy.next) # 头插法
return dummy.next3.2816. 翻倍以链表形式表示的数字
（1）栈-原地-三次遍历
# 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]:
# 栈-原地-三次遍历
# 逆序运算可以使用栈
start, end = [], [] # 运算，更新均使用栈
cur = head
# 入栈
while cur:
start.append(cur.val)
cur = cur.next
# 运算
carry = 0
while start:
carry += start.pop() * 2
end.append(carry % 10)
carry //= 10
# 更新答案
dummy = ListNode(val = carry if carry else 0, next = head)
cur = head
while cur:
cur.val = end.pop()
cur = cur.next
return dummy if dummy.val else dummy.next
（2）栈-新建链表-两次遍历
又用到了栈，又用到了头插法，又新建节点，效率不是很高。
# 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]:
# 栈-新建链表-两次遍历
start = []
cur = head
# 入栈
while cur:
start.append(cur.val)
cur = cur.next
# 运算
carry = 0
dummy = ListNode()
while start:
carry += start.pop() * 2
dummy.next = ListNode(val = carry % 10, next = dummy.next)
carry //= 10
if carry: dummy.next = ListNode(val = carry, next = dummy.next)
return dummy.next（3）反转链表-原地修改-两次遍历
# 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]:
# 反转链表-原地修改-两次遍历
# 反转链表
cur = head
pre = None
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
carry = 0
cur = pre
pre = None
while cur:
# 运算
carry += cur.val * 2
cur.val = carry % 10
carry //= 10
# 反转
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
dummy = ListNode(next = pre)
if carry: dummy.next = ListNode(val = carry, next = dummy.next)
return dummy.next（4）一次遍历
来自灵神题解（. - 力扣（LeetCode））。
# 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]:
# 一次遍历
# 总结规律
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（5）一次遍历2
来自题解（. - 力扣（LeetCode））。和（4）的解法道理是一样的，都是根据数值的范围确定只能进位一次。（4）是从上节点的角度，而（5）是从下节点的角度。
# 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]:
# 一次遍历2
dummy = ListNode(next = head)
pre = dummy
cur = head
while cur:
newVal = cur.val * 2
pre.val += newVal // 10
cur.val = newVal % 10
pre = cur
cur = cur.next
return dummy if dummy.val else dummy.next完
感谢你看到这里！一起加油吧！
![[经验] 怎么治疤痕好-疤痕治疗攻略如何有效消除疤痕 #知识分享#知识分享](https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=https%3A%2F%2Fwww.hao123rr.com%2Fzb_users%2Fcache%2Fly_autoimg%2F%25E6%2580%258E%25E4%25B9%2588%25E6%25B2%25BB%25E7%2596%25A4%25E7%2597%2595%25E5%25A5%25BD-%25E7%2596%25A4%25E7%2597%2595%25E6%25B2%25BB%25E7%2596%2597%25E6%2594%25BB%25E7%2595%25A5%25E5%25A6%2582%25E4%25BD%2595%25E6%259C%2589%25E6%2595%2588%25E6%25B6%2588%25E9%2599%25A4%25E7%2596%25A4%25E7%2597%2595.jpg&pos_id=Vn6XRLII)
