题解 | #链表的奇偶重排#
链表的奇偶重排
http://www.nowcoder.com/practice/02bf49ea45cd486daa031614f9bd6fc3
链表重排,这种题一定要画图,画着画着思路就出来了
边界条件:如果链表为空,或链表只有一个结点,或只有两个结点,直接返回head;
设置双指针,p指向奇数结点,q指向偶数结点,同时设置一个evenhead结点指向q,作为偶数链的头结点
1)让奇数结点指向偶数结点的下一个结点,同时p指针后移;
2)让偶数结点指向奇数结点的下一个结点,同时q指针后移;
3)以上两步做循环,直到奇数结点的下一个结点或偶数结点的下一个结点不存在,则退出
这里循环到最后有两种情况:
1.是原链表有奇数个结点,此时,p指向最后一个结点,q指向空结点
2.是原链表有偶数个结点,此时,p指向倒数第二个结点,q指向最后一个结点
这两种情况,p都指向奇数链表的最后一个结点,而偶数链表的尾结点的next都为nullptr
所以这两种情况可以直接合并处理,直接令奇数链表的尾结点指向偶数链表的头结点即可
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* oddEvenList(ListNode* head) { // write code here // 链表的奇偶重排 if(!head || !head->next || !head->next->next) return head; ListNode *p = head, *q = head->next, *evenhead = q; while (p->next && q->next) { p->next = q->next; p = p->next; q->next = p->next; q = q->next; } p->next = evenhead; return head; } };