【体验面试】百度真题：环形链表分成三等份
本问题对应课程链接：剑指offer刷题第二期
要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度
核心模式做就行，这里我给一个统一的方法题，注意返回值是一个容器哦，里面放三个链表的节点。
public List< ListNode > getThreeListNode(ListNode head){
}
条件说明：
1、你可以当作它存在节点，并且节点个数是3的倍数。
2、你也可以当作它存在节点，但是节点的个数不一定是 3 的倍数，如果不是，则前面分出来的链表节点多一些来处理
参考代码
代码来自于 @西西弗斯的石头 同学（稍作一些修改），当不是 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<ListNode> getThreeListNode(ListNode head){
//只有一个节点
if(head.next==head){
List<ListNode> list = new ArrayList<>();
head.next = null;//防止返回一个环形链表
list.add(head);
list.add(null);
list.add(null);
return list;
}
// 只有两个节点
if(head.next.next == head){
List<ListNode> 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<ListNode> 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<ListNode> 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
共以下 38 个回答
在只要求三等分的情况下，是否可以建立 3 个表头
然后遍历原链表，依次将节点加入这 3 个链表上
最后返回
打卡，学习一下思路
打卡，学习一下解题思路。
代码大概看得懂，核心是对节点数不是3的情况下的处理
代码就不写了，调试起来费时间
一点点思路，没有很明白，请教一下身边的人再来看1
有点思路 但是没太明白
看完方法打个卡
默认存在节点。当节点数为一，直接返回一个头。其他情况统一，采用步长为3轮流取节点（不知道这样算不算等分呢？）。这样也不需要考虑链表长度是不是3的倍数。几种情况测试均通过。
时间复杂度O(n)
空间复杂度O(1)
三指针
1. 时间复杂度：O(n)
2. 空间复杂度：O(1)
3. 代码
悄悄打个卡
大概方法理解了，就不写了
上面的代码还是有一点问题，3的倍数余1的话，链表长度会出现问题
打个卡，这个就先不做了。
统计表长，如果不是三的倍数，让指针移动到3倍数的开始，移动步长为(num-num%3)/3 记录pre结点，完成分割，不晓得对不对 时间复杂度O(n) 空间复杂度O(1)
快慢指针，用三个指针分别处理
（话说leetcode上没找到具体题目呀，有无指路~）
刚好是三的倍数的思路。
你这个方法我执行是空指针异常。。
感谢提醒，已修改
先遍历一遍看看有多少个结点，然后计算每一段一个分几个，模3运算三种情况分别处理，最后返回三个结点。
时间复杂度为O（n）,空间复杂度为O（1），三指针法
我复制评论区里简洁的代码都报空指针异常，我这个代码没问题。
用3个指针，第一个每次next一次，第二个两次，第三个三次。
当第三个到达链表尾时，第一个正好在1/3处，第二个在2/3处
思路：定义三个指针p1、p2、p3，p1一次走一步，p2一次走两步，p3一次走三步，如果环的长度正好为3的倍数，那[head, p1]就是第一段，[p1.next, p2]就是第二段, [p2.next, p3]就是第三段。如果环的长度不为3的倍数，要么多出来一个节点，要么多出来两个节点。对于多出来的一个节点，把它分给第三段，而对于多出来的两个节点，均分给第二段和第三段。时间复杂度O(N)，空间复杂度O(1)。
之前测试了下，但没放测试代码（节点数少于三个没有特殊处理，我是直接返回null），现在补上去。
解题思路：认为节点数量为3的整数倍，对于少于3个节点的情况，返回None，定义3个指针，第一个每次next一次，第二个两次，第三个三次。当第三个指针的next指向head时，第一个停在1/3处，第二个停在2/3处。
时间复杂度：O(n)
空间复杂度：O(3)
如果是三的倍数就快慢指针，三种步长，1，2，3；
如果不是三的倍数，但允许第一个多分一点，则遍历整个链表，得到size，除3得到平均长度，size取3的余数，是前面节点多的节点数
不是十分确定这道题的意思：是需要mod 3余数为0、1、2的序号分别拆出来，还是只需要分三段就行。
如果是后者，条件更加宽松，存在以下解法：
1. 快慢指针：定义三个指针，第一个走一步时，第二个走两步，第三个走三步，当三号指针重新到达头部时分割
2. 遍历计数后分割。
应该是n个节点分为3等分。如：15个节点，分成555
下面代码
时间复杂度O(n)
空间复杂度O(1)
//平分链表那块使用了两种平分方法 一种是一段一段 一种是挨个一个一个的，这块写的不是很好，请各位大佬review
节点个数是3的倍数
思路：用3个指针，第一个每次next一次，第二个两次，第三个三次。
当第三个到达链表尾时，第一个正好在1/3处，第二个在2/3处
//环形链表分成三等份。
public class Solution6 {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}
环形链表是尾节点的 next 指向 head 的链表。可以通过检测 next head 判断链表结尾。因此本题可转化为普通链表3等分的题目。
对于普通的链表3等分，我们可参考快慢指针取链表中点的方法。
我们只讨论节点个数恰好为 3 的倍数的情况，其他情况无非是边界处理的问题。
我们使用 快、中、慢 三个指针完成对链表的遍历。
快指针每次遍历3个节点，中指针每次遍历2个节点，慢指针每次遍历一个节点。
由速度关系可知，当快指针遍历至头节点（注意这是环形链表！！！）时，可知中指针在链表 2/3，慢指针在 1/3 处。
时间复杂度：O(n)
空间复杂度：O(1)
方法二：
建立 HashMap<int,Node*> 的哈希表，
计数，计算切割 1/3 和 2/3 的位置，分割链表。
时间复杂度 O(n)
空间复杂度 O(n)
P.S. 我要吐槽一下，我对「方法一比方法二更好」持怀疑态度。毕竟链表可是离散存储的结构！反复遍历链表造成的 Cache Missing 怎么说啊。很难说快指针遍历完一个节点后，等慢指针和中指针再次遍历到这个节点的时候这个节点还在不在 L1/L2/L3 Cache 里。要是这个节点已经不在 Cache 里了，那又要触发一次 Cache Missing 了，这种方法要是造成缓存行抖动，那和消耗的 O(n) 的空间来存哈希表的方案二就没任何的可比性了。
可以先遍历一遍环形链表，然后求出长度，然后确定每一段的长度，再次遍历链表，进行三等分
或者直接遍历一次链表，每次拆下一个节点将其加入结果中，这个时间会更快一下。