leetcode 328. Odd Even Linked List

原题传送门:->322. Coin Change

Description

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Constraints:

• The relative order inside both the even and odd groups should remain as it was in the input.
• The first node is considered odd, the second node even and so on …
• The length of the linked list is between [0, 10^4].

又是承认自己没有脑子的时候了。

看到调整链表(或者数组)，脑子里就只有交换结点。

但这里，是分别构造两个奇偶链表，再连接起来。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if((!head)||(!head->next)) return head;
        ListNode* oddHead = head,*oddRear = head, *evenHead = head->next,*evenRear = head->next;
        ListNode* preOddRear;
        while(oddRear->next&&evenRear->next){//判别条件:一开始我写成while(oddRear&&evenRear)
            if(evenRear->next){
                oddRear->next = evenRear->next;
                evenRear->next = nullptr;//注意这句，把尾部设为null
                oddRear = oddRear->next;
            }
            if(!oddRear->next) break;//终点为奇数
            if(oddRear->next){//终点为偶数
                evenRear->next = oddRear->next;
                evenRear = evenRear->next;
            }
        }
        oddRear->next = evenHead;
        return oddHead;
    }
};

链表问题，处处是细节。

循环跳出后各个指针是什么状态？这些需要清楚。