快慢指针问题

题目速览

参照灵神的教学视频

876.链表的中间结点
141.环形链表
142.环形链表II

题目详解

876.链表的中间结点

这题用快慢指针的话，就显得十分巧妙：当快指针指向最后一个节点或者指向为空，那么此时的慢指针指向的节点就是中间结点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow,fast = head,head
        while fast and fast.next :
            slow = slow.next
            fast = fast.next.next
        return slow
        

141.环形链表

题目解析：题目就是判断链表中是否存在环
这里我们使用 快慢指针 进行运算,所谓的快慢指针就是：开始的时候快指针和慢指针都指向头结点，然后 后续的话 慢指针每次移动一步，但是快指针每次可以移动两步，在链表中，如果出现环的话，快指针就会遇到慢指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow,fast = head,head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast is slow:
                return True
        return False

142.环形链表II

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow,fast = head,head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            # 判断是否相遇
            if fast is slow:
                # 相遇之后 让 head 和 slow 都开始运动
                while slow is not head:
                    slow = slow.next
                    head = head.next
                return slow #相遇的地方就是入口
        return None