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]
Constraints:
- The number of nodes in the linked list is in the range [ 0 , 1 0 4 ] [0, 10^4] [0,104].
- ? 1 0 6 < = N o d e . v a l < = 1 0 6 -10^6 <= Node.val <= 10^6 ?106<=Node.val<=106
From: LeetCode
Link: 328. Odd Even Linked List
Solution:
Ideas：
This function works by first checking if the head is NULL. If it’s not, it creates two pointers, odd and even, which point to the first and second nodes of the list, respectively. evenHead stores the head of the even list.
The loop continues until there are no more even nodes or even nodes with a next node. Inside the loop, the odd nodes are connected to the next odd node, and similarly, the even nodes are connected to the next even node. After the end of the loop, the odd list and the even list are connected.文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-822301.html
The final list starts with the odd nodes followed by the even nodes, as shown in your images.文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-822301.html
Code:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* oddEvenList(struct ListNode* head) {
if (head == NULL) return NULL;
struct ListNode *odd = head;
struct ListNode *even = head->next;
struct ListNode *evenHead = even;
while (even != NULL && even->next != NULL) {
odd->next = odd->next->next;
even->next = even->next->next;
odd = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
到了這里，關(guān)于LeetCode //C - 328. Odd Even Linked List的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
