【链表专题】百度真题：环形链表分成三等份
本问题对应课程链接：剑指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
共以下 17 个回答
参照题解写的，大概明白流程意思了
打卡的答案很多是不是都写错了，这是个环形链表，获取长度判断还用的nullptr
int getLength(struct node * head)
{
int length=0;
struct node * curr = head;
while( curr != NULL)
{
length++;
curr = curr->next;
if(curr head)
break;
}
return length;
}
struct node ** splitListToparts(struct node * head,int k,int returnSize)
{
struct node ** result = (struct node *)malloc(ksizeof(struct node));
int length = getLength(head);
int quotient = length/k;
int remain = length%k;
}//时间复杂度O（n），空间复杂度O（k）
时间复杂度：O(n)，空间复杂度：O(n)
特殊分类，一个，两个，三个及以上，余1，余2，三个指针用1：2：3的速度走
3个指针，如果不是3的倍数需要判断
可以用三个快慢指针，最快的指针距离头结点不足三个或正好到头结点即可等分
//通过遍历将链表一次存入3个链表中。
//时间复杂度为o(n)
//空间复杂度为o(1)
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
int sum=0;
ListNode *Count=head;
while(Count){
Count=Count->next;
sum++;
}
//sum % 3 取余。等0，等1，等于2；
ListNode *l1=new ListNode(0);
ListNode *l2=new ListNode(0);
ListNode *l3=new ListNode(0);
ListNode *p1 =l1;
ListNode *p2 =l2;
ListNode *p3 =l3;
};
時間複雜度: O(n) 空間複雜度: O(k) from chatgpt, 因為res會需要存 k段 linked list
先知道整段list多長
計算切成k段之後 一段的長度
計算除不盡的部份是幾個node
開始切分linked list 第一段要額外加上除不盡的node
ListNode* divideLinkedList(ListNode* head) {
if (!head || !head->next || !head->next->next) {
// 链表节点数小于3，无法分成三等份
return nullptr;
}
}
“`java getThreeListNode(ListNode head) { res = new ArrayList<>(3);
public List
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode p1 = dummyHead, p2 = dummyHead, p3 = dummyHead;
//利用步差，p3走最前面，只用判断p3。少于3个节点或者比三的倍数多出一个、两个节点视情况讨论
while (p3.next != head && p3.next.next != head && p3.next.next.next != head) {
p3 = p3.next.next.next;
p2 = p2.next.next;
p1 = p1.next;
}
List
if (p1 != dummyHead && p2 != dummyHead && p3 != dummyHead) {
res.add(p1);
res.add(p2);
res.add(p3);
}
return res;
}
““
时间复杂度O(n),空间复杂度O(1)
快中慢三指针
快中慢3个指针，慢指针一次走一步，中指针一次走2步，快指针，一次走3步
时间复杂度O(n)；空间复杂度O(1)
//c 多的话，每份多分一个；刚好则不管；
struct ListNode *getIntersectionNode(struct ListNode *headA){
struct ListNode *pL=headA;
struct ListNode *p1=NULL;
struct ListNode *p2=NULL;
struct ListNode *p3=NULL;
int n=1;
while(pL->next=headA){
pL=pL->next;
n++;
}
int length=0;
length=n/3;
if((n%3)!=0){
if(n%3=2){
length1=length+1;
length2=length+1;
length3=length;
}
else {
length1=length+1;
length2=length;
length3=length;
}
else{
length1=length;
length2=length;
length3=length;
}
while(length1=<0){
p1=pL;
pL=pL->next;
length–;
}while(length2=<0){
p2=pL;
pL=pL->next;
length–;
}while(length3=<0){
p3=pL;
pL=pL->next;
length–;
}
}