Leetcode — 328. Odd Even Linked List

The link to the problem: https://leetcode.com/problems/odd-even-linked-list/

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.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

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

Thoughts:

For people who are afraid of solving linked list problems, don’t worry! This problem is not hard once we draw down the steps of what we need to do.

Since the problem requires us to use O(1) space complexity to solve the problem, I’m not going to show how we use O(n) space to solve the problem here. (The logic of using O(n) space will be like we first put odd nodes in a queue and put even nodes in another queue. Then we assign nodes one by one.)

If we want to use O(1) space, we need to control the odd list and even list at the same time. We use two variables oddNode and evenNode to control what is our current node in the odd list and even list.

Code Logic:

We only do two things in each iteration.

1. Let oddNode points to the node after the current next node.
2. Let evenNode points to the node after the current next node.

After assigning the nodes to the “correct” next node, we will let them move forward and continue the process until one of them touches null. (i.e., their next node points to null)

👷For example, the original list is [1, 2, 3, 4, 5, 6, 7]

🔧Step 0. Initial Status of each variable.
Now: oddNode — 1️⃣; evenNode — 2️⃣

step 0 result

🔧Step 1. Let current nodes point to the current next node —
oddNode: 1️⃣ points to 3️⃣
evenNode: 2️⃣ points to 4️⃣

step 1 — assign next nodes process

After assigning both nodes to the current next node, we will push the nodes forward and try to do the same thing on their current next nodes.
Now: oddNode — 3️⃣; evenNode — 4️⃣

step 1 result

🔧Step 2. Let current nodes point to the current next node —
oddNode: 3️⃣ points to 5️⃣
evenNode: 4️⃣ points to 6️⃣

step 2— assign next nodes process

After assigning both nodes to the current next node, we will push the nodes forward and try to do the same thing on their current next nodes.
Now: oddNode — 5️⃣; evenNode — 6️⃣

step 2 result

🔧Step 3. Let current nodes point to the current next node —
oddNode: 5️⃣ points to 7️⃣
evenNode: 6️⃣ points to null (end of the list)

step 3 — assign next nodes process

After assigning both nodes to the current next node, we will push the nodes forward and try to do the same thing on their current next nodes.
Now: oddNode — 7️⃣; evenNode — null

step 3 result

👷Our last step will be to connect the “last node of odd list” (i.e., our current oddNode) with the “head of the even list”.

final list

public ListNode oddEvenList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode evenHead = head.next;
        ListNode evenNode = evenHead;
        ListNode oddNode = head;
        while(oddNode.next!=null && evenNode.next!=null)
        {
            oddNode.next = oddNode.next.next; 
            oddNode = oddNode.next;
            evenNode.next = evenNode.next.next;
            evenNode = evenNode.next;
        }
        oddNode.next = evenHead;
        return head;
    }

Time Complexity: O(n); Space Complexity: O(1)