# 0328. 奇偶链表
### 题目地址(328. 奇偶链表)
### 题目描述
```
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
```
### 前置知识
* 链表
### 公司
* 阿里
* 腾讯
* 百度
* 字节
### 思路
符合直觉的想法是，先遍历一遍找出奇数的节点。然后再遍历一遍找出偶数节点，最后串起来。
但是有两个问题，如果不修改节点的话，需要借助额外的空间，空间复杂度是 N。如果修改的话，会对第二次遍历（遍历偶数节点）造成影响。
因此可以采用一种做法： 遍历一次，每一步同时修改两个节点就好了，这样就可以规避上面两个问题。
### 关键点解析
* 用虚拟节点来简化操作
* 循环的结束条件设置为 `odd && odd.next && even && even.next`, 不应该是`odd && even`, 否则需要记录一下奇数节点的最后一个节点，复杂了操作
### 代码
* 语言支持：JS，C++
JavaScript Code:
```js
/*
* @lc app=leetcode id=328 lang=javascript
*
* [328] Odd Even Linked List
*
*
*/
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var oddEvenList = function (head) {
if (!head || !head.next) return head;
const dummyHead1 = {
next: head,
};
const dummyHead2 = {
next: head.next,
};
let odd = dummyHead1.next;
let even = dummyHead2.next;
while (odd && odd.next && even && even.next) {
const oddNext = odd.next.next;
const evenNext = even.next.next;
odd.next = oddNext;
even.next = evenNext;
odd = oddNext;
even = evenNext;
}
odd.next = dummyHead2.next;
return dummyHead1.next;
};
```
C++ Code：
```
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (head == nullptr) return head;
auto odd = head, evenHead = head->next, even = head->next;
// 因为“每次循环之后依然保持odd在even之前”，循环条件可以只判断even和even->next是否为空，修改odd和even的指向的操作也可以简化
while (even != nullptr && even->next != nullptr) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
};
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/328.odd-even-linked-list.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.