328. Odd Even Linked List

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @return {ListNode}
 */

题目给我们一个链表头 head

要求我们重新连接链表，把链表的奇数位置的元素往前移；把链表偶数位置的元素往后移

最后返回链表头

解题思路

为了解决这个问题，我们需要两个指针 odd、even 分别指向奇数位置的元素与偶数元素的位置

此外，还需要一个固定的指针 evenHead 来指向一开始的偶数元素位置

接下来我们的思路是，循环遍历整个链表，在每次循环中，我们要进行如下操作：

1. 把 odd.next 指向 even.next
2. 把 odd 更新为 odd.next
3. 把 even.next 指向 odd.next
4. 把 even 更新为 even.next

循环结束的条件是 even 指针或者 even.next 指向了 null，代表我们遍历到了链表的末尾

最后我们需要把 odd.next 指向一开始保存的 evenHead，把两个链表结合起来

Javascript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if(!head || !head.next) {
        return head
    }

    let odd = head
    let even = head.next
    const 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
};