題目
給定一個單鏈表，把所有的奇數(shù)節(jié)點和偶數(shù)節(jié)點分別排在一起婴谱。請注意冕屯，這里的奇數(shù)節(jié)點和偶數(shù)節(jié)點指的是節(jié)點編號的奇偶性寂诱，而不是節(jié)點的值的奇偶性。
請嘗試使用原地算法完成安聘。你的算法的空間復(fù)雜度應(yīng)為 O(1)痰洒，時間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點總數(shù)浴韭。
示例
輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
審題
1. 邏輯上丘喻，奇偶index分開，也就是分成奇數(shù)鏈表和偶數(shù)鏈表念颈，然后兩個鏈表合并泉粉。
2. 空間復(fù)雜度O(1)，不能創(chuàng)建新的鏈表榴芳。
3. 時間復(fù)雜度O(n)嗡靡，不能嵌套循環(huán)。
算法
/**
* 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 || head->next == nullptr) {
return head;
}
ListNode* odd_node = head; // 奇數(shù)鏈表
ListNode* even_node = head->next; // 偶數(shù)鏈表
ListNode* even_node_head = even_node; // 偶數(shù)鏈表頭窟感，鏈表合并使用
while (odd_node->next != nullptr && even_node->next != nullptr) {
// 奇數(shù)鏈表的next為原鏈接偶數(shù)index的next
odd_node->next = even_node->next;
odd_node = odd_node->next;
// 偶數(shù)鏈表的next為原鏈接奇數(shù)index的next
even_node->next = odd_node->next;
even_node = even_node->next;
}
// 奇偶鏈表合并
odd_node->next = even_node_head;
return head;
}
};
