当前位置：首页 > JavaScript

js实现oddevenlist

2026-01-31 20:04:04JavaScript

实现 Odd Even List 的 JavaScript 方法

Odd Even List 是一种将链表中的奇数节点和偶数节点分别排列的算法。奇数节点指的是节点位置为奇数的节点，偶数节点指的是节点位置为偶数的节点。以下是实现方法：

js实现oddevenlist

方法一：使用双指针法

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;
}

初始化 odd 指针指向头节点，even 指针指向头节点的下一个节点。
保存 even 的头节点为 evenHead，以便后续连接。
遍历链表，odd 指针连接下一个奇数节点，even 指针连接下一个偶数节点。
最后将 odd 链表的尾部连接到 even 链表的头部。

方法二：使用数组存储节点

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

    const nodes = [];
    let current = head;

    while (current !== null) {
        nodes.push(current);
        current = current.next;
    }

    const oddNodes = nodes.filter((_, index) => index % 2 === 0);
    const evenNodes = nodes.filter((_, index) => index % 2 !== 0);

    const reordered = [...oddNodes, ...evenNodes];

    for (let i = 0; i < reordered.length - 1; i++) {
        reordered[i].next = reordered[i + 1];
    }

    reordered[reordered.length - 1].next = null;
    return reordered[0];
}

遍历链表，将所有节点存入数组。
使用 filter 方法分离奇数节点和偶数节点。
合并奇数节点和偶数节点数组。
重新连接节点，形成新的链表。

方法三：递归实现

function oddEvenList(head, isOdd = true, oddHead = null, evenHead = null, oddTail = null, evenTail = null) {
    if (head === null) {
        if (oddTail !== null) oddTail.next = evenHead;
        return oddHead;
    }

    if (isOdd) {
        if (oddHead === null) {
            oddHead = head;
            oddTail = head;
        } else {
            oddTail.next = head;
            oddTail = oddTail.next;
        }
    } else {
        if (evenHead === null) {
            evenHead = head;
            evenTail = head;
        } else {
            evenTail.next = head;
            evenTail = evenTail.next;
        }
    }

    return oddEvenList(head.next, !isOdd, oddHead, evenHead, oddTail, evenTail);
}