Last Updated on 2022-12-06 by Clay
題目
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, 104]. -106 <= Node.val <= 106
題目給定一個鏈結串列（linked list），我們的任務是把所有奇數的節點重新串連在一起、偶數的節點串連在一起，最後再把奇數節點的尾端指向偶數節點們，並返回最後串連結果。
解題思路
兩節點走訪
我解題的想法是建立兩個不同的走訪節點。一個節點專門負責串連奇數節點、一個節點專門串連偶數節點；每個節點每次都會把自己的下一個節點位置，指向當前鏈結串列上自己所在位置的下下個節點。
如此一來，就會形成兩列不同的鏈結串列，最後再把奇數鏈結串列的尾端指向偶數鏈結串列即可。為了做到這件事，一開始就得分別留下奇數、偶數鏈結串列的開頭節點。
奇數節點開頭是為了最後的返回答案、偶數節點開頭是為了讓奇數節點串列尾部能找到可以指向的地方。
兩節點走訪 複雜度
| Time Complexity | O(n) |
| Space Complexity | O(1) |
因為會完整走完一趟原先的鏈結串列，故時間複雜度一定是 O(n)。不過由於我們只會宣告新的鏈結節點，故空間複雜度只會是 O(1)，有達到題目的要求。
C++ 範例程式碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
// Base case
if (!head || !head->next) {
return head;
}
// Init
ListNode* odd = head;
ListNode* even = head->next;
ListNode* oddHead = odd;
ListNode* evenHead = even;
// Traversal
while (odd->next && even->next) {
odd->next = odd->next->next;
even->next = even->next->next;
odd = odd->next;
even = even->next;
}
// Concat
odd->next = evenHead;
return oddHead;
}
};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: Optional[ListNode]) -> Optional[ListNode]:
# Base case
if not head or not head.next:
return head
# Init
odd = head
even = head.next
odd_head = odd
even_head = even
# Traversal
while odd.next and even.next:
odd.next = odd.next.next
even.next = even.next.next
odd = odd.next
even = even.next
# Concat
odd.next = even_head
return odd_head