题解 | #链表的奇偶重排#
链表的奇偶重排
http://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3
题意:
- 输入一个单链表,将该单链表奇数节点放在前半部分,偶数节点放在后半部分,不改变奇数节点和偶数节点之间的相对顺序,返回新的链表。
方法一:
解题思路:
- 一次遍历,奇数的节点组成一个链表,偶数的节点组成一个链表,然后将链表合并即可。
- oddHead,oddTail记录奇数节点链表的头尾节点;evenHead,evenTail记录偶数节点链表的头尾节点;遍历时更新oddTail,evenTail;合并时将evenHead接在oddTail之后。
图解如下:
代码如下:
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* oddEvenList(ListNode* head) { // write code here if(head==nullptr||head->next==nullptr) return head; //分别表示奇数位节点组成的链表头尾节点,以及偶数位节点组成的链表头尾节点。 ListNode *oddHead=head,*evenHead=head->next; ListNode *oddTail=head,*evenTail=evenHead; //p是遍历的临时节点 ListNode* p=head->next->next; while(true){ //p不存在则退出循环 if(!p) break; //奇数位节点 oddTail->next=p; p=p->next; oddTail=oddTail->next; if(!p) break; //偶数位节点 evenTail->next=p; p=p->next; evenTail=evenTail->next; } //连接两个链表 oddTail->next=evenHead; evenTail->next=nullptr; return oddHead; } };
复杂度分析:
时间复杂度:,遍历一次。
空间复杂度:,常数个临时变量。