难度: Medium
Submission
运行时间: 385 ms
内存: 40.2 MB
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def splitCircularLinkedList(self, head: Optional[ListNode]) -> List[Optional[ListNode]]:
#找中间节点
fast,slow=head,head
while fast.next!=head and fast.next.next!=head:
fast=fast.next.next
slow=slow.next
cur=slow.next
if fast.next==head:
fast.next=cur
elif fast.next.next==head:
fast.next.next=cur
slow.next=head
return [head,cur]
Explain
该题解采用的是快慢指针法来找到循环链表的中间节点。快指针每次移动两步，慢指针每次移动一步。当快指针的下一节点或下下一节点为头节点时，循环终止，此时慢指针所在的节点即为链表的中间节点。接下来，将链表从中间节点拆分为两部分：一部分是头节点到中间节点，另一部分是中间节点的下一个节点到链表结束。然后重新调整节点的next指针，使得两个子链表各自形成循环链表。
时间复杂度: O(n)
空间复杂度: O(1)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def splitCircularLinkedList(self, head: Optional[ListNode]) -> List[Optional[ListNode]]:
# 初始化快慢指针
fast, slow = head, head
# 快慢指针寻找中点
while fast.next != head and fast.next.next != head:
fast = fast.next.next
slow = slow.next
# 中点之后的节点
cur = slow.next
# 调整快指针指向的最后节点，使其指向中点之后的节点，形成一个循环
if fast.next == head:
fast.next = cur
elif fast.next.next == head:
fast.next.next = cur
# 调整慢指针指向头节点，使其形成一个循环
slow.next = head
# 返回两个循环链表的头节点
return [head, cur]
Explore
在使用快慢指针法寻找循环链表中点的过程中，循环结束的条件是当快指针的下一个节点或下下一个节点回到头节点时。这种终止条件确保了快指针能够遍历完整个链表，并且在遍历过程中，快指针始终保持在慢指针的前方，从而在循环结束时，慢指针位于链表中间位置的附近。
快指针的移动速度是慢指针的两倍，因此当快指针完成整个链表的一圈回到头节点时，慢指针正好走过链表的一半。当快指针的下一个节点或下下一个节点为头节点时，表示快指针已经接近或刚刚完成了一整圈的遍历。这时，慢指针因为速度较慢，所以它位于链表的大约一半的位置，这是基于链表节点总数的奇偶性来调整的精确位置。
在拆分循环链表后，为了确保每个子链表都维持循环结构，需要调整两个关键节点的`next`指针。首先，将慢指针`slow`的`next`指针指向头节点`head`，这样从头节点到慢指针形成了一个闭环。其次，将快指针`fast`在结束遍历时所在的节点的`next`指针指向慢指针的下一个节点`slow.next`，确保从这个节点开始到链表的结束再回到此节点，形成第二个闭环。这样，两个子链表各自保持了循环链表的结构。
即使链表的节点总数是奇数，快慢指针的终止条件（快指针的下一节点或下下一节点为头节点）仍然有效。在奇数节点的链表中，快指针的终止位置仍然能确保慢指针大约位于链表的中间点。这是因为快指针每次移动两步，慢指针每次移动一步，无论节点总数是奇数还是偶数，快指针回到头节点时慢指针都会位于中间位置的附近。这种方法能适应链表节点数的奇偶变化，不会影响到中间节点的正确判断。