Question

2674. 拆分循环链表

English Version

题目描述

现给定一个由正整数组成的 循环链表 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 <= 109
• LastNode.next = FirstNode ，其中 LastNode 是链表的最后一个节点，FirstNode 是第一个节点。

解法

方法一：快慢指针

我们定义两个指针 $a$ 和 $b$，初始时都指向链表的头节点。每次迭代时，指针 $a$ 向前移动一步，指针 $b$ 向前移动两步，直到指针 $b$ 到达链表的末尾。此时，指针 $a$ 指向链表节点数的一半，我们将链表从指针 $a$ 处断开，即可得到两个链表的头节点。

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

# 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]]:
    a = b = list
    while b.next != list and b.next.next != list:
      a = a.next
      b = b.next.next
    if b.next != list:
      b = b.next
    list2 = a.next
    b.next = list2
    a.next = list
    return [list, list2]

/**
 * 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 a = list, b = list;
    while (b.next != list && b.next.next != list) {
      a = a.next;
      b = b.next.next;
    }
    if (b.next != list) {
      b = b.next;
    }
    ListNode list2 = a.next;
    b.next = list2;
    a.next = list;
    return new ListNode[] {list, list2};
  }
}

/**
 * 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* a = list;
    ListNode* b = list;
    while (b->next != list && b->next->next != list) {
      a = a->next;
      b = b->next->next;
    }
    if (b->next != list) {
      b = b->next;
    }
    ListNode* list2 = a->next;
    b->next = list2;
    a->next = list;
    return {list, list2};
  }
};

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *   Val int
 *   Next *ListNode
 * }
 */
func splitCircularLinkedList(list *ListNode) []*ListNode {
  a, b := list, list
  for b.Next != list && b.Next.Next != list {
    a = a.Next
    b = b.Next.Next
  }
  if b.Next != list {
    b = b.Next
  }
  list2 := a.Next
  b.Next = list2
  a.Next = list
  return []*ListNode{list, list2}
}

/**
 * Definition for singly-linked list.
 * 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)
 *   }
 * }
 */

function splitCircularLinkedList(list: ListNode | null): Array<ListNode | null> {
  let a = list;
  let b = list;
  while (b.next !== list && b.next.next !== list) {
    a = a.next;
    b = b.next.next;
  }
  if (b.next !== list) {
    b = b.next;
  }
  const list2 = a.next;
  b.next = list2;
  a.next = list;
  return [list, list2];
}