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

要求：

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 年前 307 23

共以下 22 个回答

Marshan 普通 2023年7月13日下午11:17

//感觉可以精简？
struct ListNode{
    int val;
    ListNode *next;
    ListNode(int val):val(val),next(nullptr){}
};

vector<ListNode *> getThreeListNode(ListNode *head){
    if(head->next == head){
        vector<ListNode *>ans;
        head->next = nullptr;
        ans.push_back(head);
        ans.push_back(nullptr);
        ans.push_back(nullptr);
        return ans;
    }
    if(head->next->next == head){
        vector<ListNode *>ans;
        ListNode *temp = head->next;
        temp->next = nullptr;
        head->next = nullptr;
        ans.push_back(head);
        ans.push_back(temp);
        ans.push_back(nullptr);
        return ans;
    }
    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 *>ans;
    if((count%3) == 0){
        while(L3->next != temp){
            L3 = L3->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;
        ans.push_back(a1);
        ans.push_back(a2);
        ans.push_back(a3);
    }
    else{
        int k = count / 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;
        ans.push_back(a1);
        ans.push_back(a2);
        ans.push_back(a3);

    }
    return ans;
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月13日下午9:47

补卡（默认链表为3的倍数）

public class GetThreeListNode{
    pubilc 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 tmp = head.next;
        tmp.next = null;
        head.next = null;
        list.add(head);
        list.add(tmp);
        list.add(null);
        return list;
    }
    ListNode l1 = head;
    ListNode l1 = head.next;
    ListNode l1 = head.next.next;

    int count = 1;
    ListNode tmp = head;

    while(head.next != tmp){
        count++;
        head = head.next;
    }
    ListNode list = new ArrayList<>();
    //默认链表节点为3
    while(l3.next != tmp){
        l3 = l3.next.next.next;
        l2 = l2.next.next;
        l1 = l1.next;
    }
    ListNode a1 = l3.next;
    ListNode a2 = l1.next;
    ListNode a3 = l2.next;

    l1.next = null;
    l2.next = null;
    l3.next = null;

    list.add(a1);
    list.add(a2);
    list.add(a3);
    }
}

0 赞同 0 条回复

艺普通 2023年7月13日下午4:18

“`c++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
vector getThreeListNode(ListNode* head){
if(head->next == head)//只有一个节点
{
vector ans;
head->next = NULL;
ans.push_back(head);
ans.push_back(NULL);
ans.push_back(NULL);
return ans;
}
if(head->next->next == head)// 只有两个节点
{
vector ans;
ListNode* temp = head->next;
temp->next = NULL;
ans.push_back(temp);
head->next = NULL;
ans.push_back(head);
ans.push_back(NULL);
return ans;
}
//三节点及以上
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 ans;
if((count%3) == 0)//节点为3的倍数，用3个指针，第一个每次next一次，第二个两次，第三个三次。
//当第三个到达链表尾时，第一个正好在1/3处，第二个在2/3处
{
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;
ans.push_back(a1);
ans.push_back(a2);
ans.push_back(a3);
}else//节点不为3的倍数，将l1、l2先向前走K步，随后l3再走、直至l3.next==head
{
int k = count/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;
ans.push_back(a1);
ans.push_back(a2);
ans.push_back(a3);
}
return ans;
}

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);
cout<<“size: “<<threeListNode.size()<<endl;
for(int i=0;i<threeListNode.size();i++){
ListNode head = threeListNode[i];
cout<<“List i = “<<i<<endl;
while(head != NULL){
cout<val<<endl;
head = head->next;
}
}
}

0 赞同 0 条回复

登录以回复
mpweixin用户普通 2023年7月13日下午1:40

统计节点个数+三个指针同步走

0 赞同 0 条回复

登录以回复
NullPointerException 普通 2023年7月12日下午4:57

打卡

0 赞同 0 条回复

登录以回复

周小二普通 2023年7月11日下午11:19

public class DivideListNode {
    static class ListNode {
        ListNode(int val) {
            this.val = val;
        }

        int val;
        ListNode next;
    }

    public static List<ListNode> divideThereListNode(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 cur = head;
        // 统计节点个数
        while (cur.next!=head){
            count++;
            cur = cur.next;
        }
        // System.out.println(count);
        List list= new ArrayList<>();
        // 节点是3的倍数，三个指针，走一步，走两步，走三步来进行切分,正好三等分（需再走count/3 - 1步）
        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{
            // 7/3=2.33
            // 节点不是3的倍数，l1,l2走一步、走两步进行切分（需再走count/3 - 1步），小数0.33少走一步，小数0.66多走一步
            // 则 l2-l1 = count/3 , l3-l2 = count - 2*count/3 , l1-l3 = count/3;
            int k = (int) Math.round(count*1.0/3)-1;
            while (k!=0){
                l2 = l2.next.next;
                l1 = l1.next;
                k--;
            }
            //l3为最后一个节点
            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 条回复

今天你刷题了嘛普通 2023年7月11日下午10:37

打卡

0 赞同 0 条回复

登录以回复

#00456B 普通 2023年7月11日下午9:50

改了一个cpp版本的

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

vector<ListNode*> getThreeListNode(ListNode* head){
    if(head->next == head){
        vector<ListNode*> ans;
        head->next = NULL;
        ans.push_back(head);
        ans.push_back(NULL);
        ans.push_back(NULL);
        return ans;
    }
    if(head->next->next == head){
        vector<ListNode*> ans;
        ListNode* temp = head->next;
        temp->next = NULL;
        ans.push_back(temp);
        head->next = NULL;
        ans.push_back(head);
        ans.push_back(NULL);
        return ans;
    }
    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*> ans;
    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;
        ans.push_back(a1);
        ans.push_back(a2);
        ans.push_back(a3);
    }else{
        int k = count/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;
        ans.push_back(a1);
        ans.push_back(a2);
        ans.push_back(a3);
    }
    return ans;
}

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);
    cout<<"size: "<<threeListNode.size()<<endl;
    for(int i=0;i<threeListNode.size();i++){
        ListNode* head = threeListNode[i];
        cout<<"List i = "<<i<<endl;
        while(head != NULL){
            cout<<head->val<<endl;
            head = head->next;
        }
    }
}

0 赞同 1 条回复

#00456B 普通 @ #00456B 2023年7月12日下午1:45

用模拟的思路来做了一个

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

vector<ListNode*> getThreeListNode(ListNode* head){
    int count = 1;
    // ListNode* dummyHead = new ListNode();
    // dummyHead->next = head;
    ListNode* cur = head;
    vector<ListNode*> ans;
    while(cur->next != head){
        count++;
        cur = cur->next;
    }
    cout<<"count:"<<count<<endl;
    if(count<=3){
        cur = head;
        for(int i=0;i<count;i++){
            ListNode* node = cur;
            cur = cur->next;
            node->next = NULL;
            ans.push_back(node);
        }
        cout<<3-count<<endl;
        for(int i = 0;i<3-count;i++){
            ans.push_back(NULL);
        }
    }
    else{
        ListNode* l1 = head;
        ListNode* l2 = head->next;
        ListNode* l3 = head->next->next;
        int iter = count/3 - 1;//上面定义的时候就走了一轮了
        while(iter--){
            l1 = l1->next;
            l2 = l2->next->next;
            l3 = l3->next->next->next;
        }
        //把l1 l2 l3当作三个标识位
        //temp分别作为标识位后的截断位置
        ListNode* temp1 = l1->next;
        ListNode* temp2 = l2->next;
        ListNode* temp3 = l3->next;
        //标识位后面截断
        l1->next = NULL;
        l2->next = NULL;
        l3->next = NULL;
        //存入结果
        ans.push_back(temp1);
        ans.push_back(temp2);
        ans.push_back(temp3);
    }
    return ans;
}

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<<"List i = "<<i<<endl;
        while(head != NULL){
            cout<<head->val<<endl;
            head = head->next;
        }
    }
}

枫梓。普通 2023年7月11日下午8:18

自己写了一个根据链表尺寸来分割的函数，挺臃肿的。非3的倍数的时候没有具体细分 5 = 1 + 1 + 3 还是5 = 1 + 2 + 2，细分函数还有待考量。
时间复杂度O(n) 空间复杂度O(1)。

std::vector<Node *> getThreeList(Node *head, int size) {
    // head为链表头部， size为环链表的长度
    std::vector<Node *> ans;
    if (size == 1) {
        ans.push_back(head);
        ans.push_back(nullptr);
        ans.push_back(nullptr);
    } else {
        int single = int(size / 3);
        Node *cur = head;
        int n = 0; // 1 2 3 4
        for(int i = 0; i < 3; ++i) {
            ans.push_back(cur);
            if(i == 2) break;
            while (cur) {
                ++n;
                if (n == single) {
                    Node *next = cur->next;
                    cur->next = nullptr;
                    cur = next;
                    n = 0;
                    break;
                } else {
                    cur = cur->next;
                }
            }
        }
        Node *tmp = ans[2];
        while(tmp) {
            if(tmp->next == head) {
                tmp->next = nullptr;
                break;
            }
            tmp = tmp->next;
        }
        for(int i = 0; i < 3; i++) {
            tmp = ans[i];
            while(tmp) {
                std::cout << tmp->val << " ";
                tmp = tmp->next;
            }
            std::cout << std::endl;
        }
        return ans;
    }
}

0 赞同 0 条回复

doordie. 普通 2023年7月11日上午10:56

有点难，先打个卡，后面回来做

0 赞同 0 条回复

登录以回复
Fighting boy😀 普通 2023年7月10日下午8:38

有点费头发

0 赞同 0 条回复

登录以回复
CaCO3 永久会员 2023年7月10日下午8:20
”’java

//环形链表分成三等份
public class GetThreeListNode{
public static List GetThreeListNode(ListNode head){
//只有一个结点
if(head.next 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;
}
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{
//节点数不是3的倍数
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 条回复

登录以回复
Mooby 普通 2023年7月10日下午5:09

二

0 赞同 0 条回复

登录以回复

V2ero 普通 2023年7月10日下午3:43

还是有点难顶的。。。

const trisector = (head: ListNode | null) => {
    // 环形链表, 先处理边界，将环断开
    if (!head) {
        return [null, null, null];
    }
    // 当前节点与下一节点相同，说明只有一个节点
    if (!head.next || head.next === head) {
        head.next = null;
        return [head, null, null];
    }

    // 当前节点与下下个节点相同，说明只有两个节点
    if (head.next.next === head) {
        const next = head.next.next;
        head.next = null;
        next.next = null;
        return [head, next, null];
    }

    // 处理满足至少三个节点的情况
    let p1 = head;
    let p2 = head.next;
    let p3 = head.next.next;

    // 计算节点个数
    let cur = head.next;
    let count = 1; // 计算结束条件是当前指针是否指向头部，从头结点的后一个节点开始，所以起始数为1
    while (cur.next && cur !== head) {
        count += 1;
        cur = cur.next;
    }

    // 分情况讨论是否是3的倍数
    if (count % 3 === 0) {
        // 快中慢三个指针，迭代结束时，恰好将链表三等分
        while (p3!.next !== head) {
            p1 = p1.next!;
            p2 = p2!.next!.next!;
            p3 = p3!.next!.next!.next;
        }

        // 注意： 此时指针指向每个等分的尾部，调整指向获取头部
        let a1 = p3!.next;
        let a2 = p1!.next;
        let a3 = p2!.next;

        // 断开链
        p1.next = null;
        p2.next = null;
        p3!.next = null;

        return [a1, a2, a3];
    } else {
        let k = Math.floor(count / 3) - 1; // 决定前两等分的个数，可以通过4 4 3，3 3 4两种结果来推理

        // 结束时，p1位于的第一个等分点，p2位于第二个等分点
        while (k !== 0) {
            p1 = p1.next!;
            p2 = p2!.next!.next!;
            k -= 1;
        }

        // 指向尾部，即最后一个等分点
        while (p3!.next !== head) {
            p3 = p3!.next;
        }

        // 等分点的下一个节点，是下一段等分的开始
        let a1 = p3!.next;
        let a2 = p1!.next;
        let a3 = p2!.next;

        // 断开链
        p1.next = null;
        p2.next = null;
        p3!.next = null;

        return [a1, a2, a3];
    }
};

0 赞同 0 条回复

波雅汉库克普通 2023年7月10日下午3:12

。。不会做打卡

0 赞同 0 条回复

登录以回复

刹那芳间普通 2023年7月10日下午2:49

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;
        }
    }
}

0 赞同 0 条回复

AD钙奶普通 2023年7月10日下午2:37

public class GetThreeListNode {


    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 tmp = head.next;
            tmp.next = null;
            list.add(tmp);
            head.next = null;
            list.add(head);
            list.add(null);
            return list;
        }

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

        ListNode temp = head;
        int count = 1;
        // 统计节点个数
        while (head.next != temp) {
            count++;
            head = head.next;
        }

        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 = l1.next;
            ListNode a3 = l2.next;

            l3.next = null;
            l2.next = null;
            l1.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 = l1.next;
            ListNode a3 = l2.next;

            l3.next = null;
            l2.next = null;
            l1.next = null;

            list.add(a1);
            list.add(a2);
            list.add(a3);

        }

        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;
        List<ListNode> threeListNode = getThreeListNode(l1);
        // 打印
        for (int i = 0; i < threeListNode.size(); i++) {
            ListNode head = threeListNode.get(i);
            System.out.println("第" + i + "条链表：");
            while (head != null) {
                System.out.println(head.val);
                head = head.next;
            }
        }
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日下午12:44

打卡

0 赞同 0 条回复

登录以回复

北辰普通 2023年7月10日下午12:07

import java.util.ArrayList;
import java.util.List;

public class 环形链表分成三等分 {

    public static class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    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;
        List<ListNode> list = diviveThreeSection(l1);
        for(ListNode item:list) {
            System.out.println(item.val);
        }
    }

    public static List diviveThreeSection(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;
            head.next=null;
            temp.next=null;
            list.add(head);
            list.add(temp);
            list.add(null);
            return list;
        }
        //大于等于三个节点
        //分为两种情况：1.是3的整数倍；2.不是3整数倍
        //先统计环形链表的总结点数
        ListNode temp = head;
        int cnt = 1;
        while(temp.next!=head) {
            cnt++;
            temp = temp.next;
        }
        ListNode l1 = head;
        ListNode l2 = head.next;
        ListNode l3 = head.next.next;
        //1.是3的整数倍
        if(cnt%3==0) {
            List<ListNode> list = new ArrayList<>();
            while(l3.next!=head) {
                l3 = l3.next.next.next;
                l2 = l2.next.next;
                l1 = l1.next;
            }
            ListNode a1 = l3.next;
            ListNode a2 = l1.next;
            ListNode a3 = l2.next;
            l1.next=null;
            l2.next=null;
            l3.next=null;
            list.add(a1);
            list.add(a2);
            list.add(a3);
            return list;
        }else {//不是3的整数倍
            List<ListNode> list = new ArrayList<>();
            int k = (int)(cnt*1.0/3);
            while(k>1) {
                l1 = l1.next;
                l2 = l2.next.next;
                l3 = l3.next.next.next;
                k--;
            }
            while(l3.next!=head) l3 = l3.next;
            ListNode a1 = l3.next;
            ListNode a2 = l1.next;
            ListNode a3 = l2.next;
            l3.next = null;
            l2.next = null;
            l1.next = null;
            list.add(a1);
            list.add(a2);
            list.add(a3);
            return list;
        }
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

片言莫语普通 2023年7月9日下午10:08

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;
        }
    }
}

0 赞同 0 条回复

普通 2023年7月9日下午7:58

不是太明白啥意思

0 赞同 0 条回复

登录以回复

桎梏普通 2023年7月9日下午3:36

public List<ListNode> divideThreeList(ListNode head) {
        List<ListNode> list = new ArrayList<>(3);
        //仅一个节点
        if(head.next <span class="text-highlighted-inline" style="background-color: #fffd38;"> head) {
            head.next = null;
            list.add(head);
            list.add(null);
            list.add(null);
            return list;
        }
        //仅两个节点
        if(head.next.next </span> head) {
            ListNode tmp = head.next;
            head.next = null;
            tmp.next = null;
            list.add(head);
            list.add(tmp);
            list.add(null);
            return list;
        }
        int len = 1;
        ListNode l1 = head;
        ListNode l2 = head.next;
        ListNode l3 = head.next.next;
        while(l3.next != tmp) {
            l3 = l3.next.next.next;
            l2 = l2.next.next;
            l1 = l1.next;
        }
        ListNode a1 = l3.next;
        ListNode a2 = l1.next;
        ListNode a3 = l2.next;
        a1.next = null;
        a2.next = null;
        a3.next = null;
        list.add(a1);
        list.add(a2);
        list.add(a3);
        return list;
    }

暂未考虑非3的整数倍情况

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

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

参考代码

共以下 22 个回答

# 回答此问题 取消回复

# 回答此问题取消回复