【链表专题】百度真题：环形链表分成三等份
本问题对应课程链接：剑指offer刷题第三期
要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度
参考代码
代码来自于 @西西弗斯的石头 同学（稍作一些修改），当不是 3 的倍数时，还是比较麻烦滴。下面是一个完整的代码，包括测试，你们可以直接粘贴运行。
import java.util.*;
public class GetThreeListNode {
// 核心方法
// 当节点是 3 的倍数，则均分，当不为3的倍数，比如 1 2 3 4 5 6 7，则分成
// l1：1 2 l2:3 4 l3:5 6 7
public static List getThreeListNode(ListNode head){
//只有一个节点
if(head.next==head){
List list = new ArrayList<>();
head.next = null;//防止返回一个环形链表
list.add(head);
list.add(null);
list.add(null);
return list;
}
// 只有两个节点
if(head.next.next == head){
List list = new ArrayList<>();
ListNode temp =head.next;
temp.next = null;
list.add(temp);
head.next = null;
list.add(head);
list.add(null);
return list;
}
ListNode l1 = head;
ListNode l2 = head.next;
ListNode l3 = head.next.next;
int count =1;
ListNode temp = head;
// 统计节点个数
while (head.next!=temp){
count++;
head = head.next;
}
// System.out.println(count);
List list= new ArrayList<>();
// 节点是3的倍数，三个指针，走一步，走两步，走三步来进行切分
if((count%3)==0){
while(l3.next!=temp){
l3 = l3.next.next.next;
l2 = l2.next.next;
l1 = l1.next;
}
ListNode a1 = l3.next;
ListNode a2 = l2.next;
ListNode a3 = l1.next;
l1.next = null;
l2.next = null;
l3.next = null;
list.add(a1);
list.add(a2);
list.add(a3);
}else{
int k = (int) Math.round(count*1.0/3)-1;
while (k!=0){
l2 = l2.next.next;
l1 = l1.next;
k--;
}
while(l3.next!=temp){
l3 = l3.next;
}
ListNode a1 = l3.next;
ListNode a2 = l2.next;
ListNode a3 = l1.next;
l1.next = null;
l2.next = null;
l3.next = null;
list.add(a1);
list.add(a3);
list.add(a2);
}
return list;
}
// 测试
public static void main(String[] args) {
ListNode l1 = new ListNode(0);
ListNode l2 = new ListNode(1);
ListNode l3 = new ListNode(2);
ListNode l4 = new ListNode(3);
ListNode l5 = new ListNode(4);
ListNode l6 = new ListNode(5);
ListNode l7 = new ListNode(6);
l1.next = l1;
//l2.next = l1;
// l3.next = l4;
// l4.next = l1;
// l5.next = l6;
// l6.next = l7;
// l7.next = l1;
List threeListNode = getThreeListNode(l1);
// 打印
for(int i = 0; i < threeListNode.size(); i++){
ListNode head = threeListNode.get(i);
System.out.println("链表 i = " + i);
while(head != null){
System.out.println(head.val);
head = head.next;
}
}
}
// ListNode 内部类，用来演示需要
public static class ListNode{
int val;
ListNode next;
public ListNode(int x){
this.val = x;
}
}
}
shuaidi
共以下 29 个回答
思路：分情况讨论 getThreeListNode(ListNode head){
伪码：
public List
}
采用多指针方法（3指针，分别是每次走1/2/3跳）
【时间复杂度】O(n)
【空间复杂度】O(1)
参考的代码
先遍历一遍获取链表总长度，然后分别计算取余和商，根据商和余数得不同分为三种情况
1.取余为0则为空或者三得倍数此时等分即可
2.为1则最后一个链表长度+1
3.为2则倒数后两个长度+1
使用3个指针，fastTwoNode一次走3step，fastNode一次走2step, slowNode一次走1step；
当(head fastTwoStep && fastTwoStep != fastNode) || head fastTwoStep.next || head fastTwoStep.next.next时，三个指针到达分割点
之后就是对链表进行分割
思路：
既然要均分为三等份，则需要计算下节点的数量是否为3的倍数
是：l1、l2、l3三个指针同时走，直至l3.nexthead；
否：需要将l1、l2先向前走k步，随后l3再走、直至l3.nexthead；
k = Math.round(count*1.0/3)-1;
提问：
如果返回的三个链表都是环形链表，其中每个链表的最后一个节点会指向链表的头节点。
假设输入的链表是一个合法的环形链表。链表的节点个数是 3 的倍数，并且返回的结果列表中的链表顺序与子链表的顺序相同。
该算法首先计算链表的长度，如果长度小于3，则无法等分，直接返回空结果。然后，根据链表长度计算每个子链表的长度。接着，通过遍历找到第二个和第三个子链表的头节点，并将链表断开形成三个独立的链表。最后，将三个子链表的头节点添加到结果中并返回。
补充：用快慢指针也可以实现，fast 移动两步，slow移动一步，直到快慢指针第一次相遇，这样，fast走过的距离是slow的两倍。第一次相遇之后，将fast重新指向链表的头节点head，slow就在第一次相遇的位置，然后slow和fast同时向前走一步，直到快慢指针再次相遇。此时，slow走过的距离是链表总长度的三分之一。最后，将fast再次重新指向链表的头节点，并将第二次相遇时slow指向的位置作为第一个分割点。如此就能得到三等分的链表
时间复杂度：O(n)。
空间复杂度：O(1)。
class DetachCirCularList {
public:
vector<ListNode> getTreeListNode(ListNode head) {
if (head->next head) {
vector<ListNode*> result = { head, nullptr, nullptr };
head->next = nullptr; // 防止返回一个环形链表
return result;
}
};
时间复杂度O（N），空间复杂度O（N）
打卡
c实现
int countNodes(ListNode* head) {
if (head NULL) {
return 0;
}
}
void divideCircularList(ListNode* head) {
int count = countNodes(head);
int i;
if (count < 3) {
printf(“Not enough nodes to divide.\n”);
return;
}
}
默认链表长度为3的倍数
时间复杂度O（n）
空间复杂度O（1）
public Node threeDivide(){
// 链表长度小于3
if (headnull||head.nextnull||head.next.nextnull){
return head;
}
Node first=head.next.next;
Node second=head.next;
Node third=head;
while (first!=head){
first=first.next.next.next;
second=second.next.next;
third=third.next;
}
return third;
}
看懂了
1.能三等分，直接分
2.不能三等分，舍弃最后多出来的节点再三等分
时间：O(n)
空间：O(1)
C++
先遍历整个链表，得到链表的长度。
如果链表的长度正好可以三等份，就用三指针来做，一个走一步，一个走两步，一个走三步。
如果不可以，那么询问面试官，可以把多出来的第一个给一步，多出来的第二个给二步。
TC: O(n)
SC: O(1)
“`c++
int numNodes(ListNode* head) {
if (!head) {
return 0;
}
ListNode* curr = head;
curr = curr->next;
int num = 1;
while (curr != head) {
num++;
curr = curr->next;
}
return num;
}
vector<ListNode> divideIntoThreeParts(ListNode head) {
int numOfNodes = numNodes(head);
if (numOfNodes 0) return {NULL, NULL, NULL};
先参考一下peach同学的逻辑，暂时没想通,后面再复现
我们这样处理，先给一个函数，计算环形链表的长度，如果长度是三的倍数，证明可以三等分，如果不是三的倍数，那就不能三等分，直接返回null
或者让前面的节点个数多一些
比如余1，第一份多1；余2，第二份多1
根据情况进行处理
如果可以三等分，三个节点从头节点开始出发，1步 2步 3步，当3步节点回到头节点，三个节点的位置正好是三等分的位置
如果余1，第一份多1，那就三个一起走一步，再重复上面的过程，回到头节点就结束
如果余2，前两份多1，就三个指针一起走一步（第一份多1），再让第一个指针和第二个指针一起走一步（第二份多1）
设想是将尾部不足三等分的链表丢弃。使用三个快慢指针，node1一次走一个节点，node2一次走两个节点，node3一次走三个节点。这样每次它们之间的间隔就会加一。
node节点都指向当前链表的尾部，可以很方便地断开链表。
只遍历了一次链表，时间复杂度:O(n)
1.可以计算出能不能除3，如果能除的话，n为一分的数目，第一个结点+2n，第二个加上1n，第三个即为head结点。
2.如果不能则求余，如果余1则第一份多1，余2，则第一个结点和第二个结点都加1.
C++实现环形链表分成三等份
思路
代码
考虑是否为三等分，不是则让前面多结点。
特殊情况为：null,1,2
根据yxy的思想：与面试官讨论
– 链表是否是三等分的，是的话则三指针，一个走一步，一个走两步，一个走三步，当三步指针回到开始位置则三等分了
– 否则计算节点数%3的值，余1则这个给一步指针，让三个指针都前走一步再开始。余2则一步和二步指针各拿一个，即让三个指针都前走一步，再让三步和二步指针都前走一步再开始
与面试官讨论
– 链表是否是三等分的，是的话则三指针，一个走一步，一个走两步，一个走三步，当三步指针回到开始位置则三等分了
– 否则计算节点数%3的值，余1则这个给一步指针，让三个指针都前走一步再开始。余2则一步和二步指针各拿一个，即让三个指针都前走一步，再让三步和二步指针都前走一步再开始