# 328. Odd Even Linked List

### Leetcode

<https://leetcode.com/problems/odd-even-linked-list/>

### 題目

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.

&#x20;

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/10/oddeven-linked-list.jpg)

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

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/10/oddeven2-linked-list.jpg)

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

```
var oddEvenList = function(head) {
    if(!head) return null;
    if(!head.next || !head.next.next) return head;
    
    let pointer = head;
    let lastNode = head.next;
    const evenStartNode = lastNode;
    while(lastNode && lastNode.next) {
        const oddNode = lastNode.next;

        lastNode.next = oddNode.next;
        lastNode = oddNode.next;
        
        pointer.next = oddNode;
        oddNode.next = evenStartNode;
        pointer = pointer.next;
    }
    return head;
};
```

Runtime: 84 ms, faster than 76.58% of JavaScript online submissions for Odd Even Linked List.

Memory Usage: 41.1 MB, less than 59.92% of JavaScript online submissions for Odd Even Linked List.

For example:

head = \[1, 2, 3, 4, 5, 6, 7] -> pointer = 1， lastNode = 2，evenStartNode = 2

1. oddNode = 3， 2 -> 4，lastNode = 4，1 -> 3，3 -> 2，pointer = 3

`result: 1 -> 3 -> 2 -> 4 -> 5 -> 6 -> 7`，`pointer = 3`，`lastNode = 4`

&#x20;2\. oddNode = 5，4 -> 6，lastNode = 6，3 -> 5 -> 2，pointer = 5

`result: 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> 7`，`pointer = 5`，`lastNode = 6`

&#x20;3\. oddNode = 7，6 -> null，lastNode = null，5 -> 7 -> 2，pointer = 7

`result: 1 -> 3 -> 5 -> 7 -> 2 -> 4 -> 6 -> null`，`pointer = 7`，`lastNode = null`
