快慢指针

要点

1.快慢指针主要用来寻找链表中间节点或者处理环形链表问题

例题

# 快指针每次两步，慢指针每次一步，while条件简单分析例子得出
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow=head
        fast=head
        while fast and fast.next:
            slow=slow.next
            fast=fast.next.next
        return slow

# 有环的话，快慢指针会相遇
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow=head
        fast=head
        while fast and fast.next:
            slow =slow.next
            fast=fast.next.next
            if slow==fast:
                return True
        return False

# 关于环入口有一个结论:当快慢指针在环中相遇时，head开始移动最终会与slow在环入口相遇.
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow=head
        fast=head
        while fast and fast.next:
            slow =slow.next
            fast=fast.next.next
            if slow is fast:
                while head is not slow:
                    head=head.next
                    slow=slow.next
                return slow
        return None

# 此题是寻找中间节点和反转链表的综合.
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:

        # 中间节点
        def midNode(self,head:Optional[ListNode])->Optional[ListNode]:
            slow=head
            fast=head
            while fast and fast.next:
                slow=slow.next
                fast=fast.next.next
            return slow
        # 反转链表
        def reverseNode(self,head:Optional[ListNode])->Optional[ListNode]:
            dumpy=ListNode(next=head)
            cur=dumpy.next
            pre=None
            while cur:
                nxt=cur.next
                cur.next=pre
                pre=cur
                cur=nxt
            dumpy.next.next=cur
            dumpy.next=pre
            return dumpy.next
        mid=midNode(self,head)
        head1=head
        head2=reverseNode(self,mid)
        while head2.next:
            h1=head1.next
            h2=head2.next
            head1.next=head2
            head2.next=h1
            head1=h1
            head2=h2