反转链表

要点

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