Welcome to Subscribe On Youtube
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
whereLastNode
is the last node of the list andFirstNode
is the first one
Solutions
-
/** * 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. # 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. * 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]; }