題意:
給一個鏈表, 要求把鏈表分為兩部分, 一部分是奇數(shù)位置的數(shù), 一部分是偶數(shù)位置的數(shù). 奇數(shù)位置的數(shù)要在偶數(shù)位置的數(shù)前面, 并且數(shù)的相對位置不能改變.
解法1:
將整個鏈表拆分為奇數(shù)表和偶數(shù)表, 在從頭到尾遍歷整個鏈表的過程中, 用一個count變量進行計數(shù).
計數(shù)位置為奇數(shù)的加到奇數(shù)表里, 計數(shù)位置為偶數(shù)的加到偶數(shù)表里. 最后再把奇數(shù)表和偶數(shù)表連在一起.
時間復雜度O(n), 空間復雜度O(1)
ListNode* oddEvenList(ListNode* head) {
if (head == NULL)
return head;
ListNode* even_head;
if (head->next != NULL)
even_head = head -> next;
else
return head;
int count = 1;
ListNode *p = head->next->next;
ListNode *oddp = head;
ListNode *evenp = even_head;
while (p != NULL) {
if (count % 2 != 0) {
oddp->next = p;
oddp = oddp->next;
}
else {
evenp->next = p;
evenp = evenp->next;
}
count++;
p = p->next;
}
evenp->next = NULL;
oddp->next = even_head;
return head;
}
解法2(推薦)
解法1需要計數(shù)器, 不夠優(yōu)雅.
考慮到奇數(shù)位置后面肯定會是一個偶數(shù)位置, 所以在遍歷鏈表的過程中, 可以輪流將Node插入到奇鏈表和偶鏈表中.
在這種方法中, 需要注意空指針的排查, 詳情見注釋.
時間復雜度O(n), 空間復雜度O(1)
ListNode* oddEvenList(ListNode* head) {
if (!head)
return head;
ListNode *evenhead = head->next;
ListNode *even = evenhead;
ListNode *odd = head;
while (odd->next && even->next){ //必須先判斷奇數(shù), 再判斷偶數(shù), 因為有可能整個鏈表就一個數(shù).
odd->next = even->next; //[先] 必須先加入奇數(shù)位置, 再加入偶數(shù)位置. 因為初始化時, 偶數(shù)位置是靠奇數(shù)位置確定的.
odd = odd->next;
even->next = odd->next; //[后]
even = even->next;
}
odd->next = evenhead;
return head;
}
