grid47 Exploring patterns and algorithms
Oct 5, 2024
5 min read
Solution to LeetCode 328: Odd Even Linked List Problem
You are given the head of a singly linked list. Your task is to reorder the list such that all nodes at odd indices are grouped together followed by all nodes at even indices. The first node is considered to have an odd index, the second node is considered to have an even index, and so on. The relative order inside the odd and even groups should remain unchanged.
Problem
Approach
Steps
Complexity
Input: You are given the head of a singly linked list.
Example: head = [1, 2, 3, 4, 5]
Constraints:
• The number of nodes in the linked list is between 0 and 10^4.
• Each node's value is between -10^6 and 10^6.
Output: Return the reordered linked list where all odd-indexed nodes appear first, followed by the even-indexed nodes, while maintaining the relative order within each group.
Example: [1, 3, 5, 2, 4]
Constraints:
• The solution must operate in O(n) time complexity and use O(1) extra space.
Goal: To reorder the linked list such that all odd-indexed nodes come first, followed by the even-indexed nodes, while maintaining the relative order within both groups.
Steps:
• Initialize two pointers, one for odd-indexed nodes and one for even-indexed nodes.
• Traverse the list, separating the nodes into two lists: one for odd indices and one for even indices.
• Connect the last node of the odd list to the head of the even list.
Goal: The solution must work efficiently for large inputs with O(n) time complexity and O(1) space complexity.
Steps:
• The linked list can have up to 10^4 nodes.
• Node values can be as large as 10^6 or as small as -10^6.
Assumptions:
• The input linked list always has a valid solution.
• Input: head = [1, 2, 3, 4, 5]
• Explanation: The list groups nodes with odd indices first (1, 3, 5), followed by the nodes with even indices (2, 4).
• Input: head = [5, 10, 15, 20, 25, 30]
• Explanation: The list groups nodes with odd indices first (5, 15, 25), followed by the nodes with even indices (10, 20, 30).
Approach: To solve this problem, we can use a two-pointer technique to separate the odd and even indexed nodes while preserving their relative order.
Observations:
• We need to maintain the relative order of both odd and even indexed nodes.
• By splitting the list into two parts (odd and even indexed nodes), we can efficiently reorder them and connect them in the correct order.
Steps:
• Create two pointers, one for odd nodes and another for even nodes.
• Traverse through the list, assigning nodes to either the odd or even list.
• After processing all nodes, link the end of the odd list to the head of the even list.
Empty Inputs:
• If the list is empty, return NULL.
Large Inputs:
• For very large lists (up to 10^4 nodes), ensure that the solution runs efficiently in O(n) time.
Special Values:
• Consider cases where all nodes have the same value.
Constraints:
• The solution must handle edge cases like empty lists and lists with a single node.
This is the declaration of the `oddEvenList` function, which takes a pointer to the head of a singly linked list and returns a pointer to the reordered list.
2 : Base Case
if(!head) returnNULL;
If the head is NULL, it means the list is empty, so we return NULL immediately.
Here, three pointers are initialized: `odd` points to the first node (head), `ehead` points to the first even node (head->next), and `even` also points to the first even node.
4 : Loop Condition
while(even && even->next) {
This while loop continues as long as there are more even nodes to process (i.e., as long as `even` and `even->next` are not NULL).
5 : Odd Node Re-linking
odd->next = odd->next->next;
The next pointer of the odd node is updated to point to the next odd node, skipping over the even node.
6 : Even Node Re-linking
even->next = even->next->next;
Similarly, the next pointer of the even node is updated to point to the next even node.
7 : Pointer Advancing
odd = odd->next;
The `odd` pointer is advanced to the next odd node.
8 : Pointer Advancing
even = even->next;
The `even` pointer is advanced to the next even node.
9 : Reconnecting Odd and Even Lists
odd->next = ehead;
After processing all odd and even nodes, the last odd node's `next` pointer is set to the head of the even nodes (`ehead`), effectively linking the two sub-lists.
10 : Return Statement
return head;
Finally, the head of the modified list is returned, which now starts with all odd nodes followed by all even nodes.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is linear, as we only need to traverse the list once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, as we are not using any additional data structures that grow with the input size.
