反转链表
要点
1.在头结点前建立哨兵节点,可以免去讨论是否从头结点开始反转
2.尽量遍历一次完成反转
注意使用p0.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
下意识写的lj代码,未能一次遍历解决问题:
# 自己下意识写的lj代码,未能一次遍历解决问题
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
def reverse1(head1:Optional[ListNode])->Optional[ListNode]:
cur=head1
pre=None
while cur:
nxt=cur.next
cur.next=pre
pre=cur
cur=nxt
return pre
l=r=1
cur1=head
while r<right:
cur1=cur1.next
r+=1
tail=cur1.next
cur1.next=None
cur2=head
while l<left-1:
cur2=cur2.next
l+=1
if left>=2:
cur2.next=reverse1(cur2.next)
else:
head=reverse1(head)
# 接上尾部
r=1
cur3=head
while r<right:
cur3=cur3.next
r+=1
cur3.next=tail
return head
学习p0.next.next之后:
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
p0 = dummy = ListNode(next=head)
for _ in range(left - 1):
p0 = p0.next
pre = None
cur = p0.next
for _ in range(right - left + 1):
nxt = cur.next
cur.next = pre # 每次循环只修改一个 next
pre = cur
cur = nxt
p0.next.next = cur
p0.next = pre
return dummy.next
掌握方法后,手撸hard不是梦:
# 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]:
length=0
cur=head
while cur:
cur=cur.next
length+=1
dumpy=ListNode(next=head)
p0=dumpy
while length>=k:
length-=k
cur=p0.next
pre=None
for _ in range(k):
nxt=cur.next
cur.next=pre
pre=cur
cur=nxt
nxt1=p0.next
p0.next.next=cur
p0.next=pre
p0=nxt1
return dumpy.next
Comments NOTHING