js实现oddevenlist

实现奇偶链表

在JavaScript中实现奇偶链表，将链表的奇数节点和偶数节点分别排在一起。奇数节点指的是节点位置为奇数的节点，偶数节点指的是节点位置为偶数的节点。

方法一：分离后合并

将奇数节点和偶数节点分离成两个链表，然后将偶数链表连接到奇数链表的尾部。

function oddEvenList(head) {
    if (head === null) return null;

    let odd = head;
    let even = head.next;
    let evenHead = even;

    while (even !== null && even.next !== null) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }

    odd.next = evenHead;
    return head;
}

方法二：双指针法

使用两个指针分别跟踪奇数节点和偶数节点，逐步调整指针指向。

function oddEvenList(head) {
    if (head === null || head.next === null) return head;

    let odd = head;
    let even = head.next;
    let evenHead = even;

    while (even && even.next) {
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
    }

    odd.next = evenHead;
    return head;
}

方法三：递归实现

递归调整奇数节点和偶数节点的指向关系。

function oddEvenList(head) {
    if (head === null || head.next === null) return head;

    let odd = head;
    let even = head.next;
    let evenHead = even;

    const helper = (odd, even) => {
        if (even === null || even.next === null) {
            odd.next = evenHead;
            return head;
        }
        odd.next = even.next;
        odd = odd.next;
        even.next = odd.next;
        even = even.next;
        return helper(odd, even);
    };

    return helper(odd, even);
}

注意事项

• 输入链表为空时直接返回空。
• 链表只有一个节点时直接返回该节点。
• 确保偶数链表的头部正确连接到奇数链表的尾部。

测试用例

// 测试链表：1->2->3->4->5
const head = {
    val: 1,
    next: {
        val: 2,
        next: {
            val: 3,
            next: {
                val: 4,
                next: {
                    val: 5,
                    next: null
                }
            }
        }
    }
};

console.log(oddEvenList(head)); // 输出：1->3->5->2->4

以上方法均能有效实现奇偶链表的功能，选择适合场景的方法即可。