leetcode:环形链表分成三等份

遇到了之前某度的一道链表题，虽然只是寥寥几字但却属实不简单，特将做题思路记录下来，能力有限，如果理解有误还请大佬指出

题目描述
给一个环形链表，请你将他三等分

思路分析
对于边界值的考虑
是否满足至少三个节点的条件，对于环形链表需要注意将环断开
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 cur = head.next;
let count = 1;
while (cur.next && cur !== head) {
count += 1;
cur = cur.next;
}
是三的倍数如何进行三等分
同比寻找中点的一个常见套路，定义一个两个指针，慢指针每次走一步，快指针每次走两步，当快指针到达尾部时，慢指针刚好指向中间节点。

// 快中慢三个指针，迭代结束时，恰好将链表三等分
let p1 = head;
let p2 = head.next;
let p3 = head.next.next;
while (p3!.next !== head) {
    p1 = p1.next;
    p2 = p2.next.next;
    p3 = p3.next.next.next;
}

不是三的倍数如何进行三等分
此时每一份的数量并不一定是严格相等的，我们固定前两份的数量相同，剩下的就是最后一份的。例如链表总长度10，分为3,3,4；总长度11则为4,4,3。

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

完整代码
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];
}

};
验证代码
class ListNode {
val: number;
next: ListNode | null;
constructor(val?: number, next?: ListNode | null) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
}

const makeCircleListNode = (arr: number[]) => {
const dummy = new ListNode();
let cur = dummy;
arr.forEach(item => {
cur.next = new ListNode(item);
cur = cur.next;
});
cur.next = dummy.next;
return dummy.next;
};
const circleList = makeCircleListNode([1, 2, 3, 4, 5, 6, 7, 8, 9]);
trisector(circleList)
总结
针对普通链表，常见的有迭代和递归处理，需要判断好边界的情况
环形链表需要注意断开链，不然可能会进入死循环
双指针在栈和队列中很常见，对于快慢指针判断中点的小套路也可以引申到其他题中