Split a Circular Linked List — LeetCode 2674 Python Solution

The problem

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.

Example

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.

Python solution

# 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]

Complexity

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2674. Split a Circular Linked List is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems