123 lines
3.0 KiB
Markdown
123 lines
3.0 KiB
Markdown
## 题目地址
|
||
|
||
https://leetcode.com/problems/odd-even-linked-list/description/
|
||
|
||
## 题目描述
|
||
|
||
```
|
||
Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.
|
||
|
||
You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.
|
||
|
||
Example 1:
|
||
|
||
Input: 1->2->3->4->5->NULL
|
||
Output: 1->3->5->2->4->NULL
|
||
Example 2:
|
||
|
||
Input: 2->1->3->5->6->4->7->NULL
|
||
Output: 2->3->6->7->1->5->4->NULL
|
||
Note:
|
||
|
||
The relative order inside both the even and odd groups should remain as it was in the input.
|
||
The first node is considered odd, the second node even and so on ...
|
||
```
|
||
|
||
## 思路
|
||
|
||
符合直觉的想法是，先遍历一遍找出奇数的节点。然后再遍历一遍找出偶数节点，最后串起来。
|
||
|
||
但是有两个问题，如果不修改节点的话，需要借助额外的空间，空间复杂度是 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：
|
||
|
||
```C++
|
||
/**
|
||
* 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;
|
||
}
|
||
};
|
||
```
|