328. Odd Even Linked List

[songyy5517]

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.

Example 1:

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]

Intuition Essentially, the problem is to split the whole linked list into two sub-linked list. A straightforward idea is to use two pointers to split the linked list when looping it. Finally, concatenate the two linked list and return it.

[songyy5517]

Approach: Two Pointers

1. Exception handling;
2. Define two pointers to the first and the second node, and a head pointer to the second node;
3. Split the entire linked list into an odd linked list and an even linked list when looping;
4. Connect the two linked list end to end and return it.

Complexity Analysis

• Time complexity: $O(N)$ , splitting the entire linked list when looping it takes $O(N)$ time.
• Space complexity: $O(1)$ , additionally define constant-sized variables.

[songyy5517]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        // Intuition: Two pointers
        // 1. Exception handling
        if (head == null || head.next == null)
            return head;

        // 2. Define two pointers
        ListNode p1 = head, p2 = head.next, p2_head = head.next;

        // 3. Loop through the linked list
        while (p1.next != null && p1.next.next != null){
            p1.next = p2.next;
            p1 = p1.next;

            p2.next = p1.next;
            p2 = p2.next;
        }

        // 4. Concatenate the head of the odd list and the rear of the even list
        p1.next = p2_head;

        return head;
    }
}

[songyy5517]

2024/5/27

• End the loop when p_odd reaches the last odd element: while (p_even != null && p_even.next != null)