LeetCode 328. Odd Even Linked List

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

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 …

解析：将一个链表中的元素按照奇数位和偶数位进行重排序，奇数位在前，偶数位在后。使用两个指针，分别指向奇数位的节点和偶数位的节点。具体代码如下：

/**
 * 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 == NULL || head->next == NULL)
            return head;
        ListNode* pre=head,*cur=head->next;//pre指向奇数节点，cur指向偶数节点
        while(cur&&cur->next)
        {
            ListNode *temp = pre->next;//保存偶数位首节点，保证链表不断
            pre->next = cur->next;//指向下一个奇数位节点
            cur->next = cur->next->next;//指向下一个偶数位节点
            pre->next->next = temp;//当前奇数位节点末尾指向偶数位首节点
            pre=pre->next;//继续后移
            cur = cur->next;//继续后移
        }
        return head;
    }
};