Question

2674. Split a Circular Linked List

中文文档

Description

Given a circular linked list list of positive integers, your task is to split it into 2 circular linked lists so that the first one contains the first half of the nodes in list (exactly ceil(list.length / 2) nodes) in the same order they appeared in list, and the second one contains the rest of the nodes in list in the same order they appeared in list.

Return _an array answer of length 2 in which the first element is a circular linked list representing the first half and the second element is a circular linked list representing the second half._

A circular linked list is a normal linked list with the only difference being that the last node's next node, is the first node.

 

Example 1:

Input: nums = [1,5,7]
Output: [[1,5],[7]]
Explanation: The initial list has 3 nodes so the first half would be the first 2 elements since ceil(3 / 2) = 2 and the rest which is 1 node is in the second half.

Example 2:

Input: nums = [2,6,1,5]
Output: [[2,6],[1,5]]
Explanation: The initial list has 4 nodes so the first half would be the first 2 elements since ceil(4 / 2) = 2 and the rest which is 2 nodes are in the second half.

 

Constraints:

• The number of nodes in list is in the range [2, 105]
• 0 <= Node.val <= 109
• LastNode.next = FirstNode where LastNode is the last node of the list and FirstNode is the first one

Solutions

Solution 1: Fast and Slow Pointers

We define two pointers $a$ and $b$, both initially pointing to the head of the linked list. Each iteration, pointer $a$ moves forward one step, and pointer $b$ moves forward two steps, until pointer $b$ reaches the end of the linked list. At this point, pointer $a$ points to half of the linked list nodes, and we break the linked list from pointer $a$, thus obtaining the head nodes of the two linked lists.

The time complexity is $O(n)$, where $n$ is the length of the linked list. It requires one traversal of the linked list. The space complexity is $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];
}