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.
给定单链表，将所有奇数节点连接在一起，然后将偶数节点连接在一起。 请注意，这里我们讨论的是节点编号，而不是节点中的值。
Note: 1 ≤ m ≤ n ≤ length of list.
Examples
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL
Answer
Using total 3 nodes to traverse the list. odd to traverse all the odd index nodes, evenhead to store the head of even index node list and even to traverse the even index nodes. The next node of the current odd node is the next node of the current even node and the next node of the current even node is the next node of the current odd node.
Time Complexity
O(n) as n equals the number of nodes of input.
Space Complexity
O(1)
Code
C++
class Solution {
public: //O(1) space
ListNode* oddEvenList(ListNode* head) {
if(!head || !head->next) return head;
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenhead = head->next;
while(even && even->next)
{
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenhead;
return head;
}
};
