# LeetCode Solution, Medium, 328. Odd Even Linked List

# [328. Odd Even Linked List](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.

**Example 1:**

![oddeven-linked-list.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1656376591802/ptHUst3HE.jpeg align="left")

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

**Example 2:**

![oddeven2-linked-list.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1656376594446/ykCASK705.jpeg align="left")

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

**Constraints:**

- The number of nodes in the linked list is in the range `[0, 10**4]`.
- `-10**6 <= Node.val <= 10**6`

### 題目翻譯

今天有一個連結序列，其節點會是奇偶數交叉的排列方式，例如 `1->2->5->4`。題目需要將此序列重新排列，所有的奇數在前，後面接著所有的偶數，例如 `1->5->2->4`。

## 解法解析

解法上基本就是將原始序列分別拆成兩個奇數和偶數的序列，最後再將其連結起來。這樣的做法使用到四個變數來處理，兩個分別是記錄當前遍歷的奇偶數的位置，另外兩個則是記錄奇偶數的起始節點。

### 解法範例

#### Go

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}

	var odd *ListNode = head
	var even *ListNode = head.Next
	var evenHead *ListNode = even

	for even != nil && even.Next != nil {
		odd.Next = even.Next
		odd = odd.Next
		even.Next = odd.Next
		even = even.Next
	}
	odd.Next = evenHead
	return head
}
```

#### JavaScript

```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) {
        return null;
    }

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

#### Kotlin

```kotlin
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun oddEvenList(head: ListNode?): ListNode? {
        if (head == null) return null

        var odd: ListNode? = head
        var even: ListNode? = head.next
        var evenHead: ListNode? = 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
    }
}
```

#### PHP

```php
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution
{

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function oddEvenList($head)
    {
        if (is_null($head)) {
            return null;
        }

        $odd = $head;
        $even = $head->next;
        $evenHead = $even;

        while (!is_null($even) && !is_null($even->next)) {
            $odd->next = $even->next;
            $odd = $odd->next;
            $even->next = $odd->next;
            $even = $even->next;
        }
        $odd->next = $evenHead;
        return $head;
    }
}
```

#### Python

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode | None) -> ListNode | None:
        if head is None:
            return None

        odd: ListNode = head
        even: ListNode = head.next
        evenHead: ListNode = even

        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = evenHead
        return head
```

#### Rust

```rust
```

#### Swift

```swift
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func oddEvenList(_ head: ListNode?) -> ListNode? {
        if head == nil {
            return nil
        }

        var odd: ListNode? = head
        var even: ListNode? = head?.next
        var evenHead: ListNode? = even

        while even != nil && even?.next != nil {
            odd?.next = even?.next
            odd = odd?.next
            even?.next = odd?.next
            even = even?.next
        }
        odd!.next = evenHead
        return head
    }
}
```