2674. 拆分循环链表
现给定一个由正整数组成的 循环链表 list ，你的任务是将其拆分为 2 个 循环链表 ，使得第一个链表包含 list 前半部分 的节点（即 ceil(list.length / 2) 个节点），顺序与 list 中的顺序相同，而第二个链表包含 list 中 剩余 的节点，顺序也与 list 中的顺序相同。
返回一个长度为 2 的数组，其中第一个元素是表示 前半部分 链表的 循环链表 ，第二个元素是表示 后半部分 链表的 循环链表 。
循环链表 是一个普通的链表，唯一的区别是最后一个节点的下一个节点是头节点。
示例 1：
输入：nums = [1,5,7] 输出：[[1,5],[7]] 解释：初始链表有3个节点，因此前半部分是前两个元素，剩下的 1 个节点在后半部分。
示例 2：
输入：nums = [2,6,1,5] 输出：[[2,6],[1,5]] 解释：初始链表有4个节点，因此前半部分是前两个元素，剩下的 2 个节点在后半部分。
提示：
list 中的节点数范围为 [2, 105]0 <= Node.val <= 109LastNode.next = FirstNode ，其中 LastNode 是链表的最后一个节点，FirstNode 是第一个节点。原站题解
golang 解法, 执行用时: 172 ms, 内存消耗: 9.6 MB, 提交时间: 2023-10-16 21:23:35
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func splitCircularLinkedList(list *ListNode) []*ListNode {
fast, slow := list, list
for fast.Next != list && fast.Next.Next != list {
slow = slow.Next
fast = fast.Next.Next
}
t := slow.Next
if fast.Next == list {
fast.Next = t
}
if fast.Next.Next == list {
fast.Next.Next = t
}
slow.Next = list
return []*ListNode{list, t}
}
java 解法, 执行用时: 2 ms, 内存消耗: 55.8 MB, 提交时间: 2023-10-16 21:20:34
/**
* Definition for singly-linked list.
* 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; }
* }
*/
class Solution {
public ListNode[] splitCircularLinkedList(ListNode list) {
ListNode cur1 = list;
ListNode cur2 = list;
while (cur2.next != list && cur2.next.next != list) {
cur1 = cur1.next;
cur2 = cur2.next.next;
}
if (cur2.next != list) cur2 = cur2.next;
ListNode temp = cur1.next;
cur1.next = list;
cur2.next = temp;
return new ListNode[]{list, temp};
}
}
cpp 解法, 执行用时: 488 ms, 内存消耗: 201.3 MB, 提交时间: 2023-10-16 21:14:35
/**
* Definition for singly-linked list.
* struct ListNode {
* 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) {}
* };
*/
class Solution {
public:
vector<ListNode*> splitCircularLinkedList(ListNode* list) {
ListNode* cur1 = list;
ListNode* cur2 = list;
while (cur2->next != list and cur2->next->next != list) {
cur1 = cur1->next;
cur2 = cur2->next->next;
}
if (cur2->next != list) cur2 = cur2->next;
auto temp = cur1->next;
cur1->next = list;
cur2->next = temp;
return {list, temp};
}
};
python3 解法, 执行用时: 848 ms, 内存消耗: 50 MB, 提交时间: 2023-10-16 21:14:00
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def splitCircularLinkedList(self, head: Optional[ListNode]) -> List[Optional[ListNode]]:
fast = slow = head
while fast.next != head and fast.next.next != head:
slow = slow.next
fast = fast.next.next
t = slow.next
if fast.next == head: fast.next = t
if fast.next.next == head: fast.next.next = t
slow.next = head
return [head, t]
python3 解法, 执行用时: 744 ms, 内存消耗: 50.1 MB, 提交时间: 2023-10-16 21:13:36
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def splitCircularLinkedList(self, list: Optional[ListNode]) -> List[Optional[ListNode]]:
p1,p2,lst,f = list,list,list,1
while p2.next != list:
lst,p1 = p1,p1.next
if p2.next.next != list:
p2 = p2.next.next
f += 2
else:
p2 = p2.next
f += 1
mid = p1 if f & 1 else lst
q = mid.next
mid.next = list
p2.next = q
return [list,q]