algoadvance

Leetcode 328. Odd Even Linked List

Problem Statement

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. The program should run in O(1) space complexity and O(n) time complexity.

Example:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

• The relative order inside both the even and odd groups should remain the same as it was in the input.
• The first node is considered odd, the second node even, and so on.

Clarifying Questions

1. Q: What should be done if the linked list contains only one node? A: If the list contains only one node, it should be returned as is since there are no even-positioned nodes to rearrange.

2. Q: Can the linked list contain duplicate values? A: Yes, the values inside the linked list can be duplicates since the problem statement deals with node positions rather than values.

3. Q: Should the algorithm modify the given linked list directly or is creating a new list allowed? A: The algorithm should modify the given linked list directly to fulfill the O(1) space complexity requirement.

Strategy

1. Create two pointers, odd and even, to keep track of the end of the odd and even indexed nodes, respectively.
2. Initialize odd to head and even to head’s next node.
3. Maintain another pointer evenHead to keep the head of the even nodes.
4. Iterate through the linked list using the even pointer and reorganize the nodes as required:
   • Link the current odd node to the next odd node (i.e., odd->next = odd->next->next).
   • Link the current even node to the next even node (i.e., even->next = even->next->next).
   • Move the odd and even pointers forward.
5. At the end, link the last odd node to the head of the even nodes.

Code

Here’s the implementation of the above strategy:

/**
 * 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:
    ListNode* oddEvenList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;  // Keep track of the start of even nodes
        
        while (even && even->next) {
            odd->next = odd->next->next;  // Link odd nodes together
            even->next = even->next->next;  // Link even nodes together
            odd = odd->next;  // Move odd pointer to the next odd node
            even = even->next;  // Move even pointer to the next even node
        }
        
        odd->next = evenHead;  // Link end of odd nodes to the beginning of even nodes
        return head;
    }
};

Time Complexity

• Time Complexity: O(n) where n is the number of nodes in the linked list. We only traverse the linked list once.
• Space Complexity: O(1) because we are rearranging the nodes of the given list directly without using additional data structures.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?