【链表专题】百度真题：环形链表分成三等份

要求：

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

更新于 3 年前 246 19

共以下 19 个回答

Deckkker 普通 2024年4月27日上午10:22

思路分析

遍历链表统计长度：首先遍历链表，统计链表的长度。这是为了确定每个部分的长度以及可能存在的剩余节点数。
计算分割数量和长度：根据给定的分割数量k和链表长度，计算出每个部分的平均长度（即链表长度除以分割数量），以及前面多余的部分的长度（即链表长度对分割数量取余）。
分割链表：再次遍历链表，根据计算出的长度将链表分割成k个部分，并将每个部分的尾节点的next指针置为空。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
        if not head:
            return [None for _ in range(k)]

        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        # 计算每段的长度以及多出的部分
        avg_len, extra_len = length//k, length%k 

        # 再次遍历链表，根据 avg_len 和 extra_len 将链表分割成 k 个部分
        # 并将每个部分的尾节点的 next 指针置为空。
        res = []
        cur = head
        pre = None

        for _ in range(k):
            res.append(cur)
            for _ in range(avg_len+(1 if extra_len > 0 else 0)):
                pre = cur
                cur = cur.next
            if pre:
                pre.next = None
            extra_len -= 1
        return res

复杂度分析

时间复杂度：O(n)，其中n是链表的长度，需要遍历链表两次。
空间复杂度：O(1)

参考力扣725.分隔链表，k恒定为3即可。

0 赞同 0 条回复

e=mc² 普通 2024年3月6日下午11:57

public static List getThreeListNode(ListNode head) {
        if (head == null) {
            return null;
        }
        List<ListNode> list = new ArrayList<>();
        // 判断只有一个节点的情况
        if (head.next == head) {
            head.next = null;
            list.add(head);
            list.add(null);
            list.add(null);
        }
        // 判断只有两个节点的情况
        else if (head.next.next == head) {
            head.next.next = null;
            ListNode temp = head.next;
            head.next = null;
            list.add(head);
            list.add(temp);
            list.add(null);
        } else {
            int size = 1;
            ListNode curr = head;
            while (curr.next != head) {
                size++;
                curr = curr.next;
            }
            curr.next = null;
            int nodeSize = size / 3;
            int a = size % 3 == 0 ? 0 : size % 3;
            for (int i = 0; i < 3; i++) {
                int sum = a <= 0 ? nodeSize : nodeSize + 1;
                ListNode node = new ListNode(-1);
                ListNode temp = node;
                for (int j = 0; j < sum; j++) {
                    temp.next = head;
                    temp = temp.next;
                    head = head.next;
                }
                temp.next = null;
                list.add(node.next);
                a--;
            }
        }
        return list;
    }

时间复杂度：O(n方)
空间复杂度：O(n)

0 赞同 0 条回复

30tcq 普通 2024年3月6日下午4:43

没看懂

0 赞同 0 条回复

登录以回复
一颗红豆普通 2024年3月6日下午2:39
C++完整版代码获取步数及余数对余数情况进行处理

#include
using namespace std;
#include

class ListNode
{
public:
int val;
ListNode next;
ListNode():val(0),next(nullptr){}
ListNode(int x):val(x),next(nullptr){}
ListNode(int x,ListNode *next):val(x),next(next){}
};
vector<ListNode >getthreenode(ListNode *head)
{
int num = 1;//获取节点总数
ListNode *temp = head;
while(temp->next!=head)
{
temp = temp->next;
num++;
}
int partsize = num/3;
int remainsize = num%3;
ListNode *p1 = head;
ListNode *p2 = head->next;
ListNode *p3 = head->next->next;
if(remainsize0)
{
for(int i =1;i<partsize;i++)
{
p1 = p1->next;
p2 = p2->next->next;
p3 = p3->next->next->next;
}
}
else if(remainsize1)
{
for(int i =1;i<partsize;i++)
{
p1 = p1->next;
p2 = p2->next->next;
p3 = p3->next->next->next;
}
p3 = p3->next;
}
else
{
for(int i =1;i<partsize;i++)
{
p1 = p1->next;
p2 = p2->next->next;
p3 = p3->next->next->next;
}
p3 = p3->next;
p2 = p2->next;
}
if(p3->nexthead)
{
cout<<“节点移动正确”<<endl;
}
ListNode *head1 = p3->next;
ListNode *head2 = p1->next;
ListNode *head3 = p2->next;
p3->next = nullptr;
p2->next = nullptr;
p1->next = nullptr;
vectora(3);
cout<<a.size()<<endl;
a[0] = head1;
a[1] = head2;
a[2] = head3;
cout<<a.size()<<endl;
return a;
}

int main()
{
```
// cout<<"测试"<<endl;
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 = l2;
l2->next = l3;
l3->next = l4;
l4->next = l5;
l5->next = l6;
l6->next = l7;
l7->next = l1;
vector<ListNode *>templist = getthreenode(l1);
cout<<templist.size()<<endl;
for(int i = 0;i<templist.size();i++)
{
    ListNode *head = templist[i];
    cout<<"链表i="<<i<<endl;
    while(head!=nullptr)
    {
        cout<<head->val<<endl;
        head = head->next;
    }
}

// system("pause"); 
return 0;
```
}
0 赞同 0 条回复

登录以回复

Thaddeus 永久会员 2024年3月6日上午8:54

vector getThreeListNode(ListNode* head) {
        vector list(3);
        // 只有一个节点
        if(head->next == head) {
            head->next = nullptr;
            list[0] = head;
            list[1] = nullptr;
            list[2] = nullptr;
            return list;
        }
        // 只有两个节点
        if(head->next->next == head) {
            head->next->next = nullptr;
            list[0] = head;
            list[1] = head->next;
            list[2] = nullptr;
            return list;
        }

        ListNode *l1 = head, *l2 = head->next, *l3 = head->next->next;
        int cnt = 1;
        ListNode* tmp = head;
        // 统计节点个数
        while(head->next != tmp) {
            ++cnt;
            head = head->next;
        }

        // 情况1：节点个数是三的倍数
        if(cnt % 3 == 0) {
            while(l3->next != tmp) {
                l1 = l1->next;
                l2 = l2->next->next;
                l3 = l3->next->next->next;
            } 
        } else { // 情况2：节点个数是不是三的倍数
            int k = round(cnt * 1.0 / 3) - 1; // 各段节点数量：段1 = 段2 = 段3-1
            while(k) { // 段1和段2移动到对应位置
                l1 = l1->next;
                l2 = l2->next->next;
                --k;
            }
            while(l3->next != tmp) { // 段3再直接移动到末尾
                l3 = l3->next;
            }
        }
        ListNode *head1 = l3->next;
        ListNode *head2 = l1->next;
        ListNode *head3 = l2->next;  
        l1->next = nullptr;
        l2->next = nullptr;
        l3->next = nullptr;
        list.emplace_back(head1);
        list.emplace_back(head2);
        list.emplace_back(head3);
          

        return list;
    }

0 赞同 0 条回复

东普通 2024年3月5日下午8:41

public static List<ListNode> getThreeListNode(ListNode head){
        if(head==null){
            List<ListNode> list = new ArrayList<>();
            list.add(null);
            list.add(null);
            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;
        }
        if (count==1){
            List<ListNode> list = new ArrayList<>();
            temp.next = null;
            list.add(temp);
            list.add(null);
            list.add(null);
            return list;
        }
        if(count == 2){
            List<ListNode> list = new ArrayList<>();
            ListNode a =temp.next;
            temp.next = null;
            list.add(temp);
            a.next = null;
            list.add(a);
            list.add(null);
            return list;
        }
        System.out.println(count);
        List<ListNode> list= new ArrayList<>();
        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(a3);
            list.add(a2);
        }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;
    }

0 赞同 0 条回复

Jimmy 普通 2024年3月4日下午10:59

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

// ListNode 内部类
class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 核心方法
// 当节点是 3 的倍数，则均分，当不为3的倍数，比如 1 2 3 4 5 6 7，则分成
// l1：1 2   l2:3 4   l3:5 6 7
vector<ListNode*> getThreeListNode(ListNode* head) {
    //只有一个节点
    if (head->next == head) {
        vector<ListNode*> list(3);
        head->next = nullptr; //防止返回一个环形链表
        list[0] = head;
        list[1] = nullptr;
        list[2] = nullptr;
        return list;
    }
    // 只有两个节点
    if (head->next->next == head) {
        vector<ListNode*> list(3);
        ListNode* temp = head->next;
        temp->next = nullptr;
        list[0] = temp;
        head->next = nullptr;
        list[1] = head;
        list[2] = nullptr;
        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;
    }
    vector<ListNode*> list;
    // 节点是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 = nullptr;
        l2->next = nullptr;
        l3->next = nullptr;
        list.push_back(a1);
        list.push_back(a2);
        list.push_back(a3);
    } else {
        int k = 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 = nullptr;
        l2->next = nullptr;
        l3->next = nullptr;
        list.push_back(a1);
        list.push_back(a3);
        list.push_back(a2);
    }
    return list;
}

// 测试
int main() {
    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 = l2;
    l2->next = l3;
    l3->next = l4;
    l4->next = l5;
    l5->next = l6;
    l6->next = l7;
    l7->next = l1;
    vector<ListNode*> threeListNode = getThreeListNode(l1);
    // 打印
    for (int i = 0; i < threeListNode.size(); i++) {
        ListNode* head = threeListNode[i];
        cout << "链表 i = " << i << endl;
        while (head != nullptr) {
            cout << head->val << endl;
            head = head->next;
        }
    }
    system("pause");
    return 0;
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午10:00

java
class Solution {
public ListNode[] splitListToParts(ListNode head, int k) {
int n = 0;
ListNode temp = head;
while(temp != null){
n++;
temp = temp.next;
}
int quotient = n / k, remainder = n % k;

    ListNode[] parts = new ListNode[k];
    ListNode curr = head;
    for(int i = 0; i < k && curr != null; i++){
        parts[i] = curr;
        int partSize = quotient + (i < remainder ? 1 : 0);
        for(int j = 1; j < partSize; j++){
            curr = curr.next;
        }
        ListNode next = curr.next;
        curr.next = null;
        curr = next;
    }
    return parts;
}

}
提交

0 赞同 0 条回复

神经蛙普通 2024年3月4日下午9:50

思路:
1.先判断特殊情况，节点个数为1和2
2.节点个数为3的整数倍，使用三个快慢指针，循环直到最快的指针走到尾部时
3.节点个数不是3的整数倍，固定前两个链表的个数:节个数除3取整，最后一个链表循环到结束
4.每一个等分点的下一个节点是链表的开始，脱链

0 赞同 0 条回复

登录以回复
白雪公主倒拔垂杨柳永久会员 2024年3月4日下午9:20
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; // 长度能整出于3的最大的结果
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 = l2;
    l2.next = l3;
    l3.next = l4;
```
// l4.next = l5;
// l5.next = l6;
// l6.next = l7;
// l7.next = l1;
l4.next=l1;
```
    List<ListNode> threeListNode = getThreeListNode(l1);
    System.out.println(threeListNode);
    // 打印
    for(int i = 0; i < threeListNode.size(); i++){

        ListNode head = threeListNode.get(i); // 第i+1条的头结点
        System.out.println("开始输出第" + i+"条链表:");
        while(head != null){
            if(head.next!=null) System.out.print(head.val+"->");
            else System.out.println(head.val+"\n");
            head = head.next;
        }
    }
}

// ListNode 内部类，用来演示需要
public static class ListNode{
    int val;
    ListNode next;
    public ListNode(int x){
        this.val = x;
    }
}
```
}
0 赞同 0 条回复

登录以回复

言之命至普通 2024年3月4日下午8:33

    // 核心方法
    // 当节点是 3 的倍数，则均分，当不为3的倍数，比如 1 2 3 4 5 6 7，则分成
    // l1：1 2,3   l2:3 4,5   l3: 6 7
    public static List<ListNode> getThreeListNode(ListNode head) {
        if (head == null || head.next == head) {
            return Arrays.asList(head, null, null);
        }

        ListNode l1 = head;
        ListNode l2 = head.next;
        ListNode l3 = head.next.next;
        int count = 1;
        ListNode temp = head;

        while (temp.next != head) {
            count++;
            temp = temp.next;
        }

        List<ListNode> list = new ArrayList<>();
        if (count % 3 == 0) {
            while (l3.next != head) {
                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 = count / 3;
            while (k > 0) {
                l2 = l2.next.next;
                l1 = l1.next;
                k--;
            }
            while (l3.next != head) {
                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;
    }

0 赞同 0 条回复

Jankin 普通 2024年3月4日下午6:31

留坑，后续再学。

0 赞同 0 条回复

登录以回复

紫芝普通 2024年3月4日上午10:11

时间复杂度： O(n)
空间复杂度： O(n)

“`c++
struct Node {
int val;
Node *next;
Node(int val): val(val), next(nullptr) {}
Node(): val(0), next(nullptr) {}
};

class ThreeNodes {
public:
Node l1;
Node *l2;
Node *l3;
ThreeNodes() {
this->l1 = new Node(0);
this->l2 = new Node(0);
this->l3 = new Node(0);
}
ThreeNodes(Node l1, Node* l2, Node* l3): l1(l1), l2(l2), l3(l3) {}
~ThreeNodes() { delete l1, l2, l3; }

void SplitList(Node *head) {
    Node *c_l1 = this->l1, *c_l2 = this->l2, *c_l3 = this->l3;
    while (head) {
        c_l1->next = head;
        c_l1 = head;
        head = head->next;
        if (head) {
            c_l2->next = head;
            c_l2 = head;
            head = head->next;
            if (head) {
                c_l3->next = head;
                c_l3 = head;
                head = head->next;
            }
        }
    }
    c_l1->next = nullptr;
    c_l2->next = nullptr;
    c_l3->next = nullptr;
}
void DisplaySingleNode(Node *head) {
    if (head) {
        cout << "NodeList: ";
        while (head) {
            cout << head->val;
            head = head->next;
            if (head) cout << "->";
        }
        cout << endl;
    }
}
void Display() {
    this->DisplaySingleNode(this->l1->next);
    this->DisplaySingleNode(this->l2->next);
    this->DisplaySingleNode(this->l3->next);
}

};

“`

0 赞同 0 条回复

Yox 普通 2024年3月4日上午12:17
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);
}
```
    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;
    }
}
```
}
时间o(n) 空间o（1）
0 赞同 0 条回复

登录以回复
云无深雁影普通 2024年3月3日下午11:59

//仅为思路实现，未进行验证
//!!!此方法只需要一次遍历!!!
//使用四个指针。三个指针分别是快中慢三种速度，第四个指针在最快指针之后再多跑三格。
class Solution {
public static List getThreeListNode(ListNode head){
List ans = new ArrayList();
ListNode ptr = head;
ListNode fastPtr = headPtr;//探路指针，比最快的指针多探两格
ListNode headPtr = head;
ListNode midPtr = head;
ListNode tailPtr = head;
while(true){
tailPtr = tailPtr.next;
midPtr = midPtr.next.next;
headPtr = fastPtr.next.next.next;
fastPtr = headPtr;
if(fastPtr.next head){//下一格就是循环链表头，则说明刚好被三整除，直接断开
break;
}
if(fastPtr.next.next head){//下下格就是循环链表头，则最快指针需要多进一格
headPtr = headPtr.next;
break;
}
if(fastPtr.next.next.next head){//下下下格就是循环链表头，则中间指针需要多进一格，最快指针需要多进两格
headPtr = headPtr.next.next;
midPtr = midPtr.next;
break;
}
}
ans.add(headPtr.next);
ans.add(midPtr.next);
ans.add(fastPtr.next);
//断开链表
headPtr.next = null;
midPtr.next = null;
fastPtr.next = null;
return ans;
}
}

1 赞同 0 条回复

登录以回复

机电皮怪永久会员 2024年3月3日下午11:51

时间复杂度o（2n）
空间复杂度o（1）

“`CPP

class GetThreeListNode{
public:
//L1、L2、L3的下一个节点是被平分的链表的头节点
  ListNode L1;
  ListNode L2;
  ListNode L3;


void GetThreeListNode(ListNode* head)
  {
    if(head<span class="text-highlighted-inline" style="background-color: #fffd38;">nullptr)
    {
      return;
    }
    if(head->next=head)
    {
      L1->next=head;
      head->next=nullptr;
      return;
    }
    int total=0;
    ListNode* cur=head;
    do
    {
      cur=cur->next;
      total++;
    }
    while(cur!=head)</span>



//先分配
ListNode* tmp1=L1;
ListNode* tmp2=L2;
ListNode* tmp3=L3;
if(count%3==0)
{
  while(count>=3)
  {
    tmp1->next=cur;
    cur=cur->next;
    tmp1=tmp1->next;
    tmp1->next=nullptr;

    tmp2->next=cur;
    cur=cur->next;
    tmp2=tmp2->next;
    tmp2->next=nullptr;

    tmp3->next=cur;
    cur=cur->next;
    tmp3=tmp3->next;
    tmp3->next=nullptr;

    count=count-3;
  }
}
//count不是3的倍数
if(count==1||count==2)
{
  tmp1->next=cur;
  tmp1=tmp1->next;
  tmp1->next=nullptr;
}
if(count==2)
{
  cur=cur->next;
  tmp2->next=cur;
  tmp2=tmp2->next;
  tmp2->next=nullptr;
}

}

}

0 赞同 0 条回复

Laboratory 普通 2024年3月3日下午11:50

        public List<ListNode> getThreeListNode(ListNode head) {
            // 三指针做法
            List<ListNode> res = new ArrayList<>();
            if (head == null) {
                return res;
            }


            ListNode l1 = head;
            ListNode l2 = head.next;
            ListNode l3 = head.next.next;

            int count = 1;
            ListNode cur = head;
            while (cur.next != head) {
                count++;
                cur = cur.next;
            }
            // 当只有一个节点时
            if (count == 1) {
                head.next = null;
                res.add(head);
                res.add(null);
                res.add(null);
                return res;
            } else if (count == 2) {             // 当只有两个节点时
                ListNode node = head.next;
                head.next = null;
                node.next = null;
                res.add(head);
                res.add(node);
                return res;
            }
            // 节点为3的倍数
            else if (count % 3 == 0) {
                while (l3.next != head) {
                    l1 = l1.next;
                    l2 = l2.next.next;
                    l3 = l3.next.next.next;
                }
            } else {
                int k = (int) (Math.round(count * 1.0 / 3) - 1);
                while (k-- > 0) {
                    l1 = l1.next;
                    l2 = l2.next.next;
                }
                while (l3.next != head) {
                    l3 = l3.next;
                }
            }
            ListNode a1 = l3.next;
            ListNode a2 = l2.next;
            ListNode a3 = l1.next;
            l1.next = null;
            l2.next = null;
            l3.next = null; // 将环断开
            res.add(a1);
            res.add(a3);
            res.add(a2);

            return res;
        }

时间复杂度O(n)，空间复杂度O(1)。
重点在于理解题意，首先是环形链表，看解答的意思是首尾相接的环形链表，而不是存在环的链表，这点需要注意下。若非环形链表，分成三等分只需要两个指针就可以了，若是环形链表，则需要三个，因为需要一个指针断开环路（非环尾节点指向NULL）。题目中l3就是者这个目的。
还有就是int k = (int) (Math.round(count * 1.0 / 3) – 1); k为count除以3再取四舍五入后-1
这里让l1和l2先走k步先到达目标位置，接着让l3再走到尾节点。

0 赞同 0 条回复

进取普通 2024年3月3日下午11:35

打卡

0 赞同 0 条回复

登录以回复

Free 普通 2024年3月3日下午9:11

void cutlist(ListNode* head, ListNode*& list1, ListNode*& list2, ListNode*& list3)
{
    ListNode* tail1 = list1;
    ListNode* tail2 = list2;
    ListNode* tail3 = list3;
    int count = 1;
    ListNode* cur = head;
    while (cur)
    {
        cur = cur->next;
        count++;
    }
    int group = count / 3;
    cur = head;
    for (int i = 0; i < group; i++)
    {
        ListNode* next = cur->next;
        cur->next = tail1->next;
        tail1->next = cur;
        tail1 = tail1->next;
        cur = next;
    }
    for (int i = 0; i < group; i++)
    {
        ListNode* next = cur->next;
        cur->next = tail2->next;
        tail2->next = cur;
        tail2 = tail2->next;
        cur = next;
    }
    tail3->next = cur;
}

int main()
{
    vector<int> nums1{ 1,2,3,4,5,6 };
    ListNode* list1 = new ListNode();
    ListNode* list2 = new ListNode();
    ListNode* list3 = new ListNode();
    ListNode* head = createlist(nums1);
    printlist(head);
    cutlist(head, list1, list2, list3);
    printlist(list1->next);
    printlist(list2->next);
    printlist(list3->next);
    return 0;
}

时间复杂度O(N)
空间复杂度O(1)

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【链表专题】百度真题：环形链表分成三等份

参考代码

共以下 19 个回答

思路分析

复杂度分析

# 回答此问题 取消回复

# 回答此问题取消回复