2674. Split a Circular Linked List

Medium
Leetcode Link

Problem Description

The given problem requires us to take a circular linked list and split it into two separate circular linked lists. The circular linked list is a sequence of nodes interconnected in such a way that each node points to the next node, and the last node points back to the first node, forming a circle. We must divide this list into two halves: the first half should contain the first part of the nodes, while the second half should contain the remaining nodes. Importantly, the split is not necessarily into two equal halves; if the list has an odd number of nodes, the first half should have one more node than the second half (ceiling of half the length of the list). This split must maintain the original order of the nodes.

The resulting sublists should also be circular linked lists, where each one ends by pointing to its own first node. The output should be an array with two elements, each representing one of the halves as a circular linked list.

Intuition

To find the solution for splitting the linked list, we need to determine the point where the first list ends and the second list begins. As the linked list is circular, we can utilize the Fast and Slow pointer technique, which involves two pointers moving through the list at different speeds. The slow pointer, a, advances one node at a time, while the fast pointer, b, moves two nodes at a time.

By the time the fast pointer completes its cycle (either by reaching the initial node or the one just before it), the slow pointer, a, will be at the midpoint of the list. This is because when the fast pointer has traveled twice as far, the slow pointer has covered half the distance in the same time. The node where the slow pointer stops is where the first list will end, and the second list will begin.

Once we determine the midpoint, we then create the split. This is done by having the next node after the slow pointer be the beginning of the second linked list (list2). We must then fix the next pointers to maintain the circular nature of both lists. The next pointer of the fast pointer (b) should point to the beginning of the second list (list2), forming the second circular list. The slow pointer (a)'s next pointer should point back to the beginning of the first list, maintaining its circular nature. Finally, we return an array containing the start points of both halves of the list, preserving their circular linked list structure.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What data structure does Breadth-first search typically uses to store intermediate states?

Solution Approach

In the provided Python solution, the circular linked list is split into two halves using Floyd's Tortoise and Hare approach, which is also known for detecting cycles within linked lists. The algorithm employs two pointers: a slow pointer (a) and a fast pointer (b), as described in the intuition section.

Initially, both pointers are set to the start of the list. Then we use a while loop to continue iterating through the list as long as b (the fast pointer) doesn't meet the following conditions:

  • b.next is not the start of the list (indicating that it's not run through the entire list yet), and
  • b.next.next is not the start of the list (checking two steps ahead for the fast pointer).

Inside the loop:

  • We increment the slow pointer a by one step (a = a.next).
  • The fast pointer b increments by two steps (b = b.next.next).

When the loop exits, the slow pointer a will be at the midpoint, and the fast pointer b will be at the end of the list (or one before the end if the number of nodes is even). The if condition: if b.next != list: checks if the number of nodes is odd. If it is, then we move the fast pointer b one more node forward.

The line list2 = a.next marks the beginning of the second list by taking the node next to where the slow pointer a stopped. To form the second circular list, we set b.next = list2, linking the end of the first list to the start of the second list.

To complete the first circular list, we need to point a.next back to the head of the list (list), closing the loop on the first half of the split with a.next = list.

Finally, we return both list and list2 within an array, which are the heads of the two split circular linked lists.

To recap, here are the exact steps:

  1. Initialize two pointers a and b to the head of the circular linked list.
  2. Move a one node at a time and b two nodes at a time until b is at the end of the list or one node before the end.
  3. If the list has an odd length, increment b to point to the last node.
  4. Set list2 to the node after a, which will be the head of the second circular linked list.
  5. Link the last node of the original list to the head of the second list, forming a circular structure for the second half.
  6. Update the next pointer of the slow pointer a to the original head, forming the circular structure for the first half.
  7. Return the array [list, list2] where list is the head of the first circular list and list2 is the head of the second.

These steps allow us to achieve the desired splitting of the circular linked list while maintaining the circular nature of both resulting lists.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach for splitting a circular linked list into two halves. Suppose our circular linked list looks like this:

(Head) A -> B -> C -> D -> A

Here A is the head of the list, and the list contains four nodes. Following the steps outlined in the solution approach:

  1. Initialize two pointers a and b to the head of the circular linked list. So a = A and b = A.

  2. Start moving both pointers forward. a moves one node, and b moves two nodes at a time until b is at the end of the list or one node before the end. After the first iteration, a = B and b = C. After the second iteration, a = C and b = A (since b has moved two nodes from C and we have a circular list, it comes back to A).

  3. The list has an even length, so we don't have to increment b.

  4. Set list2 to the node after a, which will be the head of the second circular linked list. Therefore, list2 = D.

  5. Link the last node of the original list to the head of the second list to maintain the circular structure. This means we'll have C -> D -> C.

  6. Update the next pointer of the slow pointer a to the original head, which closes the loop of the first half. This means A -> B -> C -> A.

  7. Return the array [list, list2] where list is the head of the first circular list and list2 is the head of the second. As a result, we have two circular linked lists:

    • First list: (Head) A -> B -> C -> A
    • Second list: (Head) D -> C -> D

These steps demonstrate how the original circular linked list was split into two halves while ensuring that both sublists remained circular.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def splitCircularLinkedList(self, head: Optional[ListNode]) -> List[Optional[ListNode]]:
9        # Fast pointer for moving two steps at a time
10        fast_pointer = head
11        # Slow pointer for moving one step at a time
12        slow_pointer = head
13
14        # Move pointers until the fast pointer reaches the end of the list
15        while fast_pointer.next != head and fast_pointer.next.next != head:
16            slow_pointer = slow_pointer.next
17            fast_pointer = fast_pointer.next.next
18
19        # If the fast pointer is one step away from completing the cycle, move it once more
20        if fast_pointer.next != head:
21            fast_pointer = fast_pointer.next
22
23        # The slow pointer now points to the middle of the list,
24        # so we will start the second half from the next node
25        second_half_head = slow_pointer.next
26
27        # The fast pointer should now point to the second half, making it a circular list
28        fast_pointer.next = second_half_head
29
30        # The slow pointer should point to the head of the first half, completing the first circular list
31        slow_pointer.next = head
32
33        # Return the two halves, both are now circular linked lists
34        return [head, second_half_head]
35
1class Solution {
2    // The method splits a circular linked list into two halves. 
3    // If the number of nodes is odd, the extra node goes to the first half.
4    public ListNode[] splitCircularLinkedList(ListNode head) {
5        if (head == null) {
6            return new ListNode[]{null, null};
7        }
8
9        // 'slow' will eventually point to the end of the first half of the list
10        // 'fast' will be used to find the end of the list to determine the midpoint
11        ListNode slow = head, fast = head;
12
13        // Traverse the list to find the midpoint. Since it's a circular list,
14        // the conditions check if the traversed list has returned to the head.
15        while (fast.next != head && fast.next.next != head) {
16            slow = slow.next;          // move slow pointer one step
17            fast = fast.next.next;    // move fast pointer two steps
18        }
19
20        // If there are an even number of elements, move 'fast' to the very end of the list
21        if (fast.next != head) {
22            fast = fast.next;
23        }
24
25        // The 'secondHead' points to the start of the second half of the list
26        ListNode secondHead = slow.next;
27      
28        // Split the list into two by reassigning the 'next' pointers
29        fast.next = secondHead;  // Complete the second circular list
30        slow.next = head;        // Complete the first circular list
31      
32        // Return an array of the two new list heads
33        return new ListNode[]{head, secondHead};
34    }
35}
36
1#include <vector>
2
3// Definition for a node in a singly-linked list.
4struct ListNode {
5    int val;            // Value of the node.
6    ListNode *next;     // Pointer to the next node.
7
8    ListNode() : val(0), next(nullptr) {}                          // Default constructor.
9    ListNode(int x) : val(x), next(nullptr) {}                     // Constructor initializing with a value.
10    ListNode(int x, ListNode *next) : val(x), next(next) {}        // Constructor initializing with a value and the next node.
11};
12
13class Solution {
14public:
15    // Function to split a circular linked list into two halves.
16    std::vector<ListNode*> splitCircularLinkedList(ListNode* head) {
17        ListNode *slow_ptr = head;  // 'slow_ptr' will eventually point to the mid-point of the list.
18        ListNode *fast_ptr = head;  // 'fast_ptr' will be used to find the end of the list.
19
20        // Move 'fast_ptr' twice as fast as 'slow_ptr'. When 'fast_ptr' reaches the end of the list,
21        // 'slow_ptr' will be in the middle.
22        while (fast_ptr->next != head && fast_ptr->next->next != head) {
23            slow_ptr = slow_ptr->next;
24            fast_ptr = fast_ptr->next->next;
25        }
26
27        // If there are an even number of nodes, move 'fast_ptr' to the end of the list
28        if (fast_ptr->next != head) {
29            fast_ptr = fast_ptr->next;
30        }
31
32        // 'slow_ptr' is now at the splitting point so we create the second list starting after 'slow_ptr'.
33        ListNode* head2 = slow_ptr->next;
34        // The list is now split into two, with 'head2' as the head of the second list
35        // and 'head' as the head of the first list.
36        fast_ptr->next = head2;   // End of first list is now connected to the start of the second.
37        slow_ptr->next = head;    // End of second list is now connected to the start of the first.
38
39        // Return the heads of the two halves in a vector.
40        return {head, head2};
41    }
42};
43
1// This function takes a circular singly-linked list and splits it into two halves.
2// It returns an array containing the two halves of the list.
3function splitCircularLinkedList(head: ListNode | null): Array<ListNode | null> {
4    if (!head) {
5        // If the list is empty, just return an array with two null elements.
6        return [null, null];
7    }
8  
9    let slowPointer: ListNode | null = head; // This will move one step at a time.
10    let fastPointer: ListNode | null = head; // This will move two steps at a time.
11  
12    // Move through the list to find the middle
13    // Fast pointer moves twice as fast as the slow pointer.
14    // When the fast pointer reaches the end, slow pointer will be at the middle.
15    while (fastPointer.next !== head && fastPointer.next.next !== head) {
16        slowPointer = slowPointer.next;
17        fastPointer = fastPointer.next.next;
18    }
19  
20    // In case of an even number of elements
21    // move the fast pointer one more step to reach the end of the list.
22    if (fastPointer.next !== head) {
23        fastPointer = fastPointer.next;
24    }
25  
26    // Now, slowPointer is at the end of the first half of the list.
27    // The node following slowPointer starts the second half.
28    const secondHalfHead: ListNode | null = slowPointer.next;
29  
30    // Split the list into two halves.
31    // The first half will end at the slowPointer and should circle back to the head.
32    slowPointer.next = head;
33  
34    // The second half starts at secondHalfHead and will end at the fastPointer.
35    fastPointer.next = secondHalfHead;
36  
37    // Return the two halves of the list.
38    return [head, secondHalfHead];
39}
40
41// Definition for singly-linked list (provided for context).
42class ListNode {
43    val: number;
44    next: ListNode | null;
45    constructor(val?: number, next?: ListNode | null) {
46        this.val = (val === undefined ? 0 : val);
47        this.next = (next === undefined ? null : next);
48    }
49}
50
Not Sure What to Study? Take the 2-min Quiz：

Which of the following is the prefix sum of array [1, 2, 3, 4, 5]?

Time and Space Complexity

The given code snippet is designed to split a circular singly linked list into two halves. The algorithm uses the fast and slow pointer technique, also known as Floyd's cycle-finding algorithm, to identify the midpoint of the list.

Time Complexity:

The time complexity of this algorithm can be determined by analyzing the while loop, which continues until the fast pointer (b) has either completed a cycle or is at the last node.

  • In each iteration of the loop, the slow pointer (a) moves one step, and the fast pointer (b) moves two steps.
  • In the worst case scenario, the fast pointer might traverse the entire list before the loop terminates. This would be the case if the number of elements in the list is odd.
  • If the list has n nodes, and since the fast pointer moves two steps at a time, it will take O(n/2) steps for the fast pointer to traverse the entire list.
  • Therefore, the time complexity of the loop is O(n).

Space Complexity:

The space complexity of this algorithm refers to the additional space used by the algorithm, not including space for the input itself.

  • The only extra variables used are the two pointers, a and b. These do not depend on the size of the input list but are rather fixed.
  • Therefore, the space complexity of the algorithm is O(1).

In summary, the time complexity is O(n) and the space complexity is O(1).

Fast Track Your Learning with Our Quick Skills Quiz:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫