tags: leetcode medium Linked List

328. Odd Even Linked List

Description

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Examples

Example1

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Constraints:

• The number of nodes in the linked list is in the range $[0, 10^4]$
• $-10^6 \leq Node.val \leq 10^6$ .

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode LISTNODE;

struct ListNode* oddEvenList(struct ListNode* head) {
    // Under three node just return list
    if ((!head) || (!head->next) || (!head->next->next))
        return head;
    // Initialize pointers
    LISTNODE *lastOdd = head, *firstEven = lastOdd->next,
             *lastEven = lastOdd->next;
    // Run until find the last odd node or the last even node
    while (lastEven && lastEven->next) {
        // Find the next odd node
        lastOdd = lastOdd->next = lastEven->next;
        // Add even node to even-list
        lastEven = lastEven->next = lastOdd->next;
    }
    // Concate the odd list and even  list
    lastOdd->next = firstEven;
    return head;
}

Complexity

Space	Time
$O(1)$	$O(N)$

Result

• Runtime: 4 ms, 92.68%
• Memory: 7.1 MB, 25.30%