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以上方法均能有效实现奇偶链表的功能，选择适合场景的方法即可。
