Solution: Problem Challenge 2: Rearrange a LinkedList

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 2: Rearrange a LinkedList

Table of Contents

Contents are not accessible

Problem Statement

Given the head of a Singly LinkedList, write a method to modify the LinkedList such that the nodes from the second half of the LinkedList are inserted alternately to the nodes from the first half in reverse order. So if the LinkedList has nodes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null, your method should return 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null.

Your algorithm should use only constant space the input LinkedList should be modified in-place.

Example 1:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> 12 -> null
Output: 2 -> 12 -> 4 -> 10 -> 6 -> 8 -> null

Example 2:

Input: 2 -> 4 -> 6 -> 8 -> 10 -> null
Output: 2 -> 10 -> 4 -> 8 -> 6 -> null

Constraints:

The number of nodes in the list is in the range [ $1, 5 * 10^4$ ].
1 <= Node.val <= 1000

Solution

This problem shares similarities with Palindrome LinkedList. To rearrange the given LinkedList we will follow the following steps:

We can use the Fast & Slow pointers method similar to Middle of the LinkedList to find the middle node of the LinkedList.
Once we have the middle of the LinkedList, we will reverse the second half of the LinkedList.
Finally, we’ll iterate through the first half and the reversed second half to produce a LinkedList in the required order.

Here is the visual representation of this algorithm for Example-1:

Code

Here is what our algorithm will look like:

Python3

. . . .

Complexity Analysis

Time Complexity

Finding the middle of the linked list: The algorithm uses the two-pointer technique (slow and fast pointers) to find the middle of the linked list. This phase takes $O(N)$ time, where N is the number of nodes in the linked list.
Reversing the second half: After finding the middle, the algorithm reverses the second half of the list. This takes $O(N/2)$ time, which simplifies to $O(N)$ .
Merging the two halves: Once the second half is reversed, the algorithm merges the first and second halves of the linked list. Each node is processed exactly once during this merging phase, so this part also takes $O(N)$ .

Overall time complexity: $O(N)$ , where N is the number of nodes in the linked list.

Space Complexity

The algorithm modifies the linked list in place, and no extra space is used other than the pointers (slow, fast, prev, etc.).
The space required for these variables is constant, so the space complexity is $O(1)$ .

Overall space complexity: $O(1)$ (constant space).

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible