328. Odd Even Linked List

---

My Solution

The Key Idea for Solving This Coding Question

C++ Code

/**
 * 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 == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode *odd = head, *even = head->next;
        ListNode *oddIt = head, *evenIt = head->next;

        while (oddIt->next != nullptr && evenIt->next != nullptr) {
            oddIt->next = evenIt->next;
            oddIt = oddIt->next;
            evenIt->next = oddIt->next;
            evenIt = evenIt->next;
        }
        oddIt->next = even;

        head = odd;
        return head;
    }
};

Time Complexity

Space Complexity

C++ Code 2

 /**
 * 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, *itOdd = odd;
        ListNode *even = head->next, *itEven = even;
        while (itOdd->next && itEven->next) {
            itOdd->next = itEven->next;
            itOdd = itOdd->next;
            if (!itOdd || !itOdd->next) {
                break;
            }
            
            itEven->next = itOdd->next;
            itEven = itEven->next;
        }
        
        itOdd->next = even;
        itEven->next = nullptr;
        head = odd;
        
        return head;
    }
};

Time Complexity

Space Complexity

Miscellaneous