题解 | #链表的奇偶重排#
链表的奇偶重排
http://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3
问题描述
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。
注意是节点的编号而非节点的数值。
数据范围：节点数量满足 0≤n≤105，节点中的值都满足 0≤val≤1000
要求：空间复杂度 O(n)，时间复杂度O(n)
如果按照题目要求的空间复杂度为O(n),那么很简单，只需要重新建一个尾插的单链表放偶数
位的节点。假设原链表只存奇数位的节点，然后遍历结束后，原链表尾部最后接上新建链表
的头部就可以了。
那么我们可不可以想办法让空间复杂度变为O(1)呢？
我们只需要定义两个指针odd(奇数位指针)，even(偶数位指针)。奇数位开始指向头节点，偶数
位指针开始指向头节点的下一个节点。然后只要even!=null&&even->next!=null，就做如下操作：
odd->next=even->next, odd=odd->next; even->next=odd->next,even=even->next;
在循环体内不用担心指针会越界，因为循环判断条件已经限定了当even=null或even->next=null
以1->2->3->4->5->null和1->2->3->4->5->6->null为例
第一次：odd 1->3->4->5->null，ood指向3，1-> 3->4->5->6->null;odd指向3
even 2->4->5->null， even指向4，2->4->5->6->null; even指向4
第二次：odd 1->3->5->null， odd指向5，1->3->5->6->null; odd指向5
even 2->4->null， evec指向null， 2->4->6->null; evec指向6
当链表长度为奇数时，是以veve==null退出循环，此时odd指针指向的是5，只需要odd->next指向
even的头节点。
当链表长度为偶数时，是以even->next==null退出循环，此时odd指针指向5，也只需要odd->next
指向even的头节点。
那么又会出现一个新问题，even的头结点在哪儿，只需要开始的时候定义一个指针ehead指向head->next，
这样ehead就是even的头节点。
最后让odd->next=ehead就行了。
复杂度分析：
时间复杂度：O(n)，只需要(n-1)/2次就结束循环了。
空间复杂度O(1)，常数个变量，且没有额外申请空间。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if(head==NULL||head->next==NULL) return head;
ListNode *odd,*even,*ehead;
odd=head,even=head->next;
ehead=even;
while(even!=NULL&&even->next!=NULL){
odd->next=even->next;
odd=odd->next;
even->next=odd->next;
even=even->next;
}
odd->next=ehead;
return head;
}
};
查看9道真题和解析
投递中国国际金融股份有限公司等公司10个岗位 >