34. Reverse Even-Indexed Nodes and Append

Origin: Reverse Even-Indexed Nodes and Append

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

Example

Input: head = [10, 20, 30, 40, 50, 60]

Output: [20, 40, 60, 50, 30, 10]

Explanation:

• Step 1: 提取偶数索引（0, 2, 4）→ [10, 30, 50]
• Step 2: 剩余奇数索引节点 → [20, 40, 60]
• Step 3: 反转提取的节点 → [50, 30, 10]
• Step 4: 追加到末尾 → [20, 40, 60, 50, 30, 10]

注意：0-indexed，偶数索引是 0, 2, 4…（第一个节点算索引 0）。

Input Format

• 第一行：n（链表长度）
• 接下来 n 行：每行一个节点的值

Constraints

• 0 <= n <= 100000
• -10^9 <= 节点值 <= 10
• 偶数索引节点：0, 2, 4, …
• 链表可能为空（n=0）

Output Format

返回修改后链表的值数组。

Sample Input 0

1
42

Sample Output 0

42

Sample Input 1

2
1 2

Sample Output 1

2 1

---

函数契约

// 输入：链表头节点（或数组表示）
// 输出：修改后链表的值数组
// 边界：空链表 → []；单节点 → [该节点值]；两节点 → [第二个, 第一个]

边界表

场景	返回什么
空链表	[]
单节点 [42]	[42]
两节点 [1, 2]	[2, 1]
三节点 [10, 20, 30]	[20, 10, 30]
正常	奇数索引在前 + 反转的偶数索引在后

Resolution

我的解法

function extractAndAppendSponsoredNodes(head: SinglyLinkedListNode): SinglyLinkedListNode {
    if (!head) return head
    const arr = []
    let cur = head
    while (cur) {
        arr.push(cur.data)
        cur = cur.next!
    }
 
    const evenArr = []
    const prefixArr = []
 
    for (let i = 0; i < arr.length; i++) {
        if (i % 2) {
            prefixArr.push(arr[i])
        } else {
            evenArr.push(arr[i])
        }
    }
 
    const dummy: SinglyLinkedListNode = new SinglyLinkedListNode(0);
    let resHead = dummy;
 
    [...prefixArr, ...evenArr.reverse()].forEach((data) => {
        resHead.next = new SinglyLinkedListNode(data)
        resHead = resHead.next
    })
 
    return dummy.next!
}

解题思路

链表只是包装，本质是数组操作：

1. 遍历链表收集所有值到数组
2. 按索引奇偶拆分：奇数索引 → prefixArr，偶数索引 → evenArr
3. 反转 evenArr，拼接到 prefixArr 后面
4. 用 dummy 节点重建链表

dummy 节点是链表题的常用技巧：创建一个虚拟头节点，依次往后挂新节点，最后返回 dummy.next。避免单独处理头节点为空的边界。

复杂度

• 时间：O(n)，遍历一次收集 + 一次重建
• 空间：O(n)，存两个子数组

标准解法（指针操作，O(1) 空间）

function extractAndAppendSponsoredNodes(head: SinglyLinkedListNode): SinglyLinkedListNode {
    if (!head) return head
 
    const dummy = new SinglyLinkedListNode(0)
    let oddTail = dummy          // 奇数链的尾指针
    let evenHead = null          // 偶数链的头（头插法反转）
    let cur = head
    let index = 0
 
    while (cur) {
        const next = cur.next
        if (index % 2 === 0) {
            // 偶数索引：摘下来，头插到 evenHead（自动反转）
            cur.next = evenHead
            evenHead = cur
        } else {
            // 奇数索引：挂到奇数链尾部
            cur.next = null
            oddTail.next = cur
            oddTail = cur
        }
        cur = next
        index++
    }
 
    // 奇数链尾部接上反转后的偶数链
    oddTail.next = evenHead
 
    return dummy.next
}

遍历一次链表，偶数节点头插（自动反转），奇数节点尾插，最后拼接。不需要额外数组，O(1) 空间。头插法是链表反转的经典技巧：每次把新节点插到头部，遍历完就自动反转了。

参考来源

• 相关文章：算法解题流程：从读题到提交的七步
• 相关题型：链表解题（如果有）
• 相关题目：12. Remove Consecutive Duplicates from Sorted Linked List — 链表操作基础