等长分割循环链表
[!Tip]
本节源代码见Github链接🔗
问题描述
如何把一个循环链表分割成两个长度相等的部分？如果链表的结点数是奇数，那么让第一个链表的结点数比第二个多1个。
核心思路
参考08-找到链表的中间结点，用移速不同的两个指针，找到中间结点，然后将链表分割为两个循环链表。包含以下3步：
- 定义两个指向头结点的指针slowPtr和fastPtr，以不同的速度向前移动指针，slowPtr每次移动一个结点，fastPtr每次移动两个结点；
- 当fastPtr移动到末尾时停止移动，此时slowPtr正指向中间结点；
- 将fastPtr的后继指针指向slowPtr的后继结点，将slowPtr的后继指针指向链表头结点。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 等长分割循环链表
*
* @param headNode
* @author: Max Solider
* @date: 2022/10/11 22:39
*/
void splitCircularList(NormalListNode headNode) {
if (headNode == null || headNode.getNext() == null || headNode.getNext() == headNode) {
System.out.println("The linked list cannot be divided into two.");
return; }
NormalListNode slowPtr = headNode;
NormalListNode fastPtr = headNode;
while (fastPtr.getNext() != headNode && fastPtr.getNext().getNext() != headNode) {
slowPtr = slowPtr.getNext();
fastPtr = fastPtr.getNext().getNext();
}
if (fastPtr.getNext() != headNode) {
fastPtr = fastPtr.getNext();
}
NormalListNode aList = headNode;
NormalListNode bList = slowPtr.getNext();
slowPtr.setNext(aList);
fastPtr.setNext(bList);
listLength(aList);
System.out.println("========");
listLength(bList);
}
时间复杂度
时间复杂度为O(n)，用于遍历链表。
空间复杂度
空间复杂度为O(1)，用于存储临时变量。