7.20 Reverse Even-Indexed Nodes and Append

7.20.1 Problem Metadata

7.20.2 Description

Given a singly linked lc-list, extract all even-indexed nodes (0-indexed), reverse their order, and append them to the end of the lc-list in one traversal. Return the head of the modified lc-list.

Note: Even indices refer to positions 0, 2, 4, … (not even values). The problem statement refers to these as “sponsored nodes.”

7.20.3 Examples

Example 1:

Input:
  head = [10, 20, 30, 40, 50, 60]
Output:
  [20, 40, 60, 50, 30, 10]
Explanation:
  - Step 1: Extract nodes at even positions 0, 2, 4 → [10, 30, 50]
  - Step 2: Remaining nodes at odd positions 1, 3, 5 → [20, 40, 60]
  - Step 3: Reverse the extracted lc-list → [50, 30, 10]
  - Step 4: Append reversed lc-list to remaining → [20, 40, 60, 50, 30, 10]

Example 2:

Input:
  head = [42]
Output:
  [42]
Explanation:
  Single node lc-list. Even-indexed node [42] reversed is still [42].
  No odd-indexed nodes to prepend, so result is [42].

Example 3:

Input:
  head = [1, 2]
Output:
  [2, 1]
Explanation:
  - Even-indexed nodes: [1]
  - Odd-indexed nodes: [2]
  - Reverse [1] → [1]
  - Append → [2, 1]

7.20.4 Input Format

  • First line: integer n denoting the length of linked lc-list
  • Next n lines: elements of the linked lc-list

Example:

6
10
20
30
40
50
60

7.20.5 Constraints

  • \(0 \le n \le 100000\)
  • \(-10^9 \le\) value of each node \(\le 10^9\)
  • Even indices are 0, 2, 4, … (0-indexed)
  • The lc-list may be empty (n = 0)

7.20.6 Output Format

An array representing the values of the modified linked lc-list.

7.20.7 Sample Input 0

1
42

7.20.8 Sample Output 0

42

Explanation: Single node at index 0 (even). After reversal and appending, result is [42].

7.20.9 Sample Input 1

2
1
2

7.20.10 Sample Output 1

2
1

Explanation: Node 1 at index 0 (even), node 2 at index 1 (odd). After extraction and reversal: [2, 1].

7.20.11 Solution - Extract, Reverse, and Append

7.20.11.1 Walkthrough

This solution uses a three-phase approach to efficiently solve the problem in O(n) time:

  1. Phase 1: Separate even and odd indexed nodes - Use two pointers to extract nodes at even positions (0, 2, 4, …) into one lc-list and nodes at odd positions (1, 3, 5, …) into another lc-list
  2. Phase 2: Reverse the even-indexed lc-list - Apply iterative reversal to the extracted even-indexed nodes
  3. Phase 3: Append reversed lc-list - Connect the tail of the odd-indexed lc-list to the head of the reversed even-indexed lc-list

Key Insight: The odd-indexed lc-list becomes the new head of the result, with the reversed even-indexed lc-list appended to its tail.

Visual Example 1: head = [10, 20, 30, 40, 50, 60]

Phase 1: Separation

Initial state:
[10] → [20] → [30] → [40] → [50] → [60] → null
 ^even  ^odd
 ^evenHead  ^oddHead

Iteration 1:
  oddTail = odd (20)
  even.next = odd.next (30)
  even moves to 30
  odd.next = even.next (40)
  odd moves to 40

State after iteration 1:
Even lc-list: [10] → [30] ...
Odd lc-list:  [20] → [40] ...
           ^oddTail

Iteration 2:
  oddTail = odd (40)
  even.next = odd.next (50)
  even moves to 50
  odd.next = even.next (60)
  odd moves to 60

State after iteration 2:
Even lc-list: [10] → [30] → [50] ...
Odd lc-list:  [20] → [40] → [60] ...
                  ^oddTail

Iteration 3:
  oddTail = odd (60)
  even.next = odd.next (null)
  even moves to null
  Loop exits (even is null)

Final separated state:
Even lc-list: [10] → [30] → [50] → null
Odd lc-list:  [20] → [40] → [60] → null
                         ^oddTail

Phase 2: Reverse even lc-list

Reverse [10] → [30] → [50] → null

Step 1: prev=null, curr=10
  next = 30
  10.next = null
  prev = 10, curr = 30

Step 2: prev=10, curr=30
  next = 50
  30.next = 10
  prev = 30, curr = 50

Step 3: prev=30, curr=50
  next = null
  50.next = 30
  prev = 50, curr = null

Result: [50] → [30] → [10] → null
        ^evenHead (updated)

Phase 3: Connect odd tail to reversed even head

Odd lc-list:     [20] → [40] → [60] → null
                            ^oddTail

Reversed even: [50] → [30] → [10] → null
               ^evenHead

After oddTail.next = evenHead:
[20] → [40] → [60] → [50] → [30] → [10] → null
^oddHead

Return oddHead → [20, 40, 60, 50, 30, 10] ✓

Visual Example 2: head = [1, 2]

Phase 1: Separation
Initial: [1] → [2] → null
         ^even  ^odd
         ^evenHead  ^oddHead

Iteration 1:
  oddTail = odd (2)
  even.next = odd.next (null)
  even moves to null
  Loop exits

Separated:
Even: [1] → null
Odd:  [2] → null
      ^oddTail

Phase 2: Reverse even lc-list
[1] → null (already reversed, single node)
^evenHead

Phase 3: Connect
oddTail.next = evenHead
[2] → [1] → null
^oddHead

Return [2, 1] ✓

Visual Example 3: head = [42]

Edge case: Single node
even = 42, evenHead = 42
odd = null, oddHead = null

Early return: head.next == null, return head
Result: [42] ✓

Edge Case: Empty lc-list

head = null
Return null immediately ✓

7.20.11.2 Analysis

  • Time Complexity: O(n)
    • Phase 1 (Separation): O(n) - visits each node once to separate into two lc-lists
    • Phase 2 (Reversal): O(n/2) - reverses approximately half the nodes (even-indexed)
    • Phase 3 (Connection): O(1) - single pointer assignment
    • Overall: O(n)
  • Space Complexity: O(1)
    • Uses only a constant number of pointers (even, evenHead, odd, oddHead, oddTail, prev, curr, next)
    • No additional data structures or recursion
    • All operations modify pointers in-place

7.20.11.3 Implementation Steps

  1. Handle edge cases:
    • Return null if head is null
    • Return head if only single node exists
  2. Initialize pointers for separation:
    • even starts at index 0 (head)
    • evenHead saves the head of even lc-list
    • odd starts at index 1 (head.next)
    • oddHead saves the head of odd lc-list (this becomes the final result head)
    • oddTail tracks the last node of odd lc-list for appending
  3. Separate even and odd nodes:
    • While both even and odd are non-null:
      • Track oddTail before advancing
      • Link even.next to skip the odd node
      • Move even to next even-indexed node
      • If even is not null, link odd.next to skip the even node and advance odd
  4. Reverse the even-indexed lc-list:
    • Use iterative three-pointer reversal (prev, curr, next)
    • Update evenHead to the new head after reversal
  5. Connect odd tail to reversed even head:
    • Set oddTail.next = evenHead
  6. Return the new head:
    • Return oddHead (the head of the odd-indexed lc-list)

7.20.11.4 Code - Java

class Result {

    /*
     * Complete the 'extractAndAppendSponsoredNodes' function below.
     *
     * The function is expected to return an INTEGER_SINGLY_LINKED_LIST.
     * The function accepts INTEGER_SINGLY_LINKED_LIST head as parameter.
     */

    /*
     * For your reference:
     *
     * SinglyLinkedListNode {
     *     int data;
     *     SinglyLinkedListNode next;
     * }
     *
     */

    public static SinglyLinkedListNode extractAndAppendSponsoredNodes(SinglyLinkedListNode head) {
        if (head == null) {
            return null;
        }
        
        if(head.next == null) {
            return head;
        }

        // starts at index 0
        SinglyLinkedListNode even = head;        
        SinglyLinkedListNode evenHead = even;
        // starts at index 1 (or null)
        SinglyLinkedListNode odd = head.next;    
        SinglyLinkedListNode oddHead = odd;      
        SinglyLinkedListNode oddTail = null;

        while (even != null && odd != null) {
            oddTail = odd;
            even.next = odd.next;         // skip odd node
            even = even.next;             // move to next even node (or null)
            
            //make sure even is not null
            if (even != null) {                          
                odd.next = even.next;     // skip even node                
                odd = odd.next;           // move to next odd node (or null)
            }
        }
        
        evenHead = reverseList(evenHead);
        oddTail.next = evenHead;
        
        return oddHead;
    }
    
    private static SinglyLinkedListNode reverseList(SinglyLinkedListNode head) {
        SinglyLinkedListNode prev = null;
        SinglyLinkedListNode curr = head;
        
        while (curr != null) {
            SinglyLinkedListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }

}