LeetCode 328 Odd Even Linked List（奇偶链表）（Linked List）（*）

翻译

给定一个单链表，将所有的奇节点归为一组，偶节点紧随其后。

请注意我们现在谈的是奇节点而不是节点上的值。

你应该尝试就地完成。

程序应该在O(1)空间复杂度和O(nodes)时间复杂度下完成。

例如：
给定 1->2->3->4->5->NULL，
返回 1->3->5->2->4->NULL。

注释：
最后归类出来的奇节点和偶节点的相对位置应该和输入时一致。

第一个节点为奇节点，第二个节点为偶节点，以此类推……

原文

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:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:

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 ...

分析

寒假第一题，农村老家真的超冷……我想的思路可能不是太简洁，再加上考虑的不全面，导致不断的出错、调试、出错、调试……最终花了好久才完成，而代码已经谈不上简洁了。

ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next) return head;
    bool oddFlag = true;          
    ListNode* odd = head;
    ListNode* even = head->next;
    ListNode* oddHead = odd;
    ListNode* evenHead = even;
    head = head->next->next;      
    while (head) {
        if (oddFlag) {
            odd->next = head;
            odd = odd->next;
            oddFlag = false;
        }
        else {
            even->next = head;
            even = even->next;
            oddFlag = true;
        }
        head = head->next;
    }
    if (!oddFlag)
        even->next = NULL;
    odd->next = evenHead; 
    return oddHead;
}

过程叻大概是这样的：

1，判断是否为空，两种情况都返回head。
2，新建odd和even来不断遍历，和head一样，它们三个是会移动的。
3，oddHead和evenHead是不会动的，用于最后拼凑新的链表。
4，用isOdd来判断当前的节点是否是奇节点，不管是不是，它们的操作都是类似的。
5，最后的时候，如果是奇节点结尾的，那么可能偶节点最后一个会是多余的，所以需要将它干掉。
6，拼凑新的链表用于返回。

然而仔细想想呢，其实还有很大的改善空间，比如说：

既定义了oddHead还定义了evenHead，有一个很好的解决方案是：用head来作为oddHead。这样在返回的时候我们就可以直接返回head了，那么新的问题来了？之前我们是用的head来进行迭代的，那么现在呢？我们需要找到一种新的解决办法。

我们来回顾一下之前的算法：用head来遍历每一个节点，用一个bool变量来标志这个节点的性质（奇节点还是偶节点）。举个例子：

1，2，3，4，5，NULL

我们发现奇节点的下一个节点恰好就是偶节点的下一个节点（1的下一个节点应该是2的下一个节点，也就是3），而偶节点的下一个节点也恰好是奇节点是下一个节点。这样我们就可以只通过odd和even两个变量来遍历了，既省去了用来遍历的head，也省去了一个变量oddHead，同时还可以直接返回head，何乐而不为呢？

还记得上面我们用了这样一步吗？

if (!isOdd)
    even->next = NULL;
odd->next = evenHead; 

如果按照现在的思路，那么也完全不需要这个判断了，因为在求next的过程中，已经将该用NULL的地方设置成了NULL。

所以代码修改成：

ListNode* oddEvenList(ListNode* head) {
    if (!head) return head;    
    ListNode* odd = head;
    ListNode* even = head->next;
    ListNode* evenHead = even;   
    while (odd->next && even->next) {
        odd->next = even->next;
        odd = odd->next;    
        even->next = odd->next;
        even = even->next;
    }
    odd->next = evenHead;
    return head;
}

while循环中间的部分的顺序可不能颠倒了，只有更新了odd之后，才能将odd->next的设为even->next。

代码

C Plus Plus

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (!head) return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even;
        while (odd->next && even->next) {
            odd->next = even->next;
            odd = odd->next;
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

Java

updated at 2016/09/20

    public ListNode oddEvenList(ListNode head) {
        if (head == null) return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while (odd.next != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }