題目敘述
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:
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]
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
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
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
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
class Solution
{
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
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
Swift
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
}
}