目录
一、学习视频
【反转链表】 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 pre
2.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.next
3.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 newhead
2.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.next
3.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
完
感谢你看到这里!一起加油吧!