Leedcode 328. Odd Even Linked List

题目描述：

    Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

 

Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

 题解：

       
       这里添加代码

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        ListNode* oddNums_head = new ListNode(0);
        ListNode* evenNums_head = new ListNode(0);
        ListNode* evenNums_ptr = evenNums_head;
        ListNode* oddNums_ptr = oddNums_head;
        ListNode* curr = head;
        int n = 1;
        while(curr != nullptr){
            if(n%2 == 0){
                evenNums_ptr->next = curr;
                evenNums_ptr = evenNums_ptr->next;
            }else{
                oddNums_ptr->next = curr;
                oddNums_ptr = oddNums_ptr->next;
            }
            ++n;
            curr = curr->next;
        }
        oddNums_ptr->next = evenNums_head->next;
        evenNums_ptr->next = nullptr;
        ListNode* res = oddNums_head->next;
        delete oddNums_head;
        delete evenNums_head;
        return res;
    }
};
	
	
	

...这道题整体的解题方法和leedcode中的 86号问题是一样的。

    先定义了两个虚拟头节点 oddNums_head, evenNums_head用于连接单数和双数，再连接这两个指针指向的所有节点。

    最后删除头节点。

用int型元素n来记录指针head指向的当前节点是单数还是双数。