Javascript(leetcode#328) Odd Even Linked List

Difficult:Medium

題目

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

翻譯

給定單向鍊錶的頭部，將所有具有奇數索引的節點組合在一起，然後是具有偶數索引的節點，並返回重新排序的列表。

第一個節點被認為是奇數，第二個節點是偶數，依此類推。

請注意，偶數組和奇數組內的相對順序應保持與輸入中相同。

您必須解決 O(1) 額外空間複雜​​度和 O(n) 時間複雜度的問題。

範例

Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

解題思路

1. 設odd的link list變數
2. 最後將分離的兩個link list組合起來

程式碼

var oddEvenList = function (head) {
    if (head == null) return head;
    let num = 1;
    let odd = null;
    let oddhead = null;
    let headnode = head;
    let last;
    let pre = null;

    while (head) {
        if (num % 2 == 0) {
            let temp = pre;
            pre.next = head.next;
            if (oddhead == null) {
                oddhead = head;
                oddhead.next = null;
                odd = oddhead;
            } else {
                odd.next = head;
                odd = odd.next;
                odd.next = null;
            }
            pre = head;
            head = temp.next;

        } else {
            pre = head;
            last = head;
            head = head.next;
        }
        num++;
    }

    last.next = oddhead;
    return headnode;
};