leetcode 328. Odd Even Linked List

328. Odd Even Linked List

自己最开始的思路：用两个指针分别指向奇偶位置，然后交换两个的数值，然后奇的指针前进两格，偶的指针前进一格，但是这样出来的结果会造成原本偶位置的数之间的顺序打乱

正确的思路：也是用奇偶指针，但是是将偶后面的链表节点移动到奇后面，这样不发生顺序的变换。当前的两个指针分别指向当前排好的最后一个奇位置和最后一个偶位置，这个地方就有点像数组那种的做法了。

https://www.cnblogs.com/grandyang/p/5138936.html

错误代码：

cur一直是当前偶数的最后一个排好的，这样交换会丢掉所有之前拍好的偶数位的，用排好的奇数位的最后一个的下一个就好，因为你放奇数也是放在排好的最后一个奇数位的后面

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* pre = head;
        ListNode* cur = head->next;
        while(cur != NULL && cur->next != NULL){
            pre->next = cur->next;
            cur->next = pre->next->next;
            pre->next->next = cur;
            pre = pre->next;
            cur = cur->next;
        }
        return head;
    }
};

正确代码：

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* pre = head;
        ListNode* cur = head->next;
        while(cur != NULL && cur->next != NULL){
            ListNode* tmp = pre->next;
            pre->next = cur->next;
            cur->next = pre->next->next;
            pre->next->next = tmp;
            pre = pre->next;
            cur = cur->next;
        }
        return head;
    }
};