【链表专题】百度真题：环形链表分成三等份
本问题对应课程链接：剑指offer刷题第七期
要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度
参考代码
下面是一个完整的代码，包括测试，你们可以直接粘贴运行。
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
共以下 18 个回答
测试demo
结果：
打印开始----------------------》
1 -> 2
打印结束----------------------》
打印开始----------------------》
3 -> 4
打印结束----------------------》
打印开始----------------------》
5 -> 6
打印结束----------------------》
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.nexthead){
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);
}
// 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;
}
}
}
}
用三个指针遍历链表，拆分环
待理解…
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public ListNode[] splitCircularList(ListNode head) {
if (head null) return new ListNode[3];
//计算链表长度
int n = 1;
ListNode cur = head;
while(cur.next != head) {
cur = cur.next;
n++;
}
““java
帅地的看不太懂，看了评论区的一个答案完全看懂了
主要看不懂的就是那个count/3-1，现在明白就是为了尽可能均分三个链表的长度，非常感谢
package com.sky.annotation;
import java.util.ArrayList;
import java.util.List;
public class GetThreeListNode {
}
““java
帅地的看不太懂，看了评论区的一个答案完全看懂了
主要看不懂的就是那个count/3-1，现在明白就是为了尽可能均分三个链表的长度，非常感谢
package com.sky.annotation;
import java.util.ArrayList;
import java.util.List;
public class GetThreeListNode {
}
待理解
时间复杂度：O(n)
空间复杂度：O(1)
这个题目说实话光这么一行字很难体现全部要求 比如不能被整除的时候结果要怎么分配
这里以7 —> (2, 2, 3)为例
思路：计量长度，然后整除3取得前两list的长度，然后分割。思路是这样 细节也不少 需要回顾加深理解。
time O(n) space O(n)
思路
复杂度分析
遍历链表计算长度 O(n)，分配节点 O(n)，总复杂度为 O(n)。
空间复杂度
只使用了固定数量的指针，空间复杂度为 O(1)。
思路： 首先统计节点数量，若小于3个 则直接返回每个结点。 若大于3个结点，则设置三个链表，cueernt1 = head; current2 = head.next; current3 = head.next.next; 每次移动 三步。 首先移动 3的整数轮，最后剩余节点一定小于3， 依次加入 current1 和 current2 即可
思路：本题所指的环形链表是最后一个节点的 next 指针指向链表的第一个节点，形成一个闭环的链表。从一个环形链表中 k 等份，即将该链表分解成 k 个子链表，每个子链表的长度尽可能等长，如果链表长度不能被 k 整除，最后一个子链表就会包含剩余的所有节点。
① 计算环形链表的长度，并对边界条件进行处理。
② 划分链表，计算每个子链表的长度为
groupSize = len / k，这样能够保证只有最后一个子链表长度不同，其他的子链表长度等长。先对前k - 1个子链表进行划分，长度为groupSize，并将每个子链表的头节点添加至list中，并且每个子链表之间并不存在连接关系。nextGroupHead最后指向的就是最后一个子链表的头节点，最后一个子链表包含剩余的所有节点，将其头节点添加至list中。时间复杂度：O(n)，遍历整个链表一次，划分链表时也遍历了一次。
空间复杂度：O(k)，使用了一个
ArrayList来存储每个子链表的头节点。