设计一个算法，将一个结点值为自然数的单链表拆分为两个单链表，原表中保留值为偶数的结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。

可以使用两个指针分别指向偶数链表和奇数链表的尾部，遍历原链表，将偶数结点插入偶数链表，奇数结点插入奇数链表，最后将两个链表连接起来即可。

具体实现如下：

ListNode* oddEvenList(ListNode* head) {
if (!head) return head;
ListNode *evenHead = head->next, *oddTail = head, *evenTail = evenHead;
while (evenTail && evenTail->next) {
oddTail->next = evenTail->next;
oddTail = oddTail->next;
evenTail->next = oddTail->next;
evenTail = evenTail->next;
}
oddTail->next = evenHead;
return head;
}

这个算法的时间复杂度是 O(n)，空间复杂度是 O(1)。

相关问题

设计一个算法,将一个结点值自然数的单链表拆分为两个单链表,原表中保留值为偶数的

可以使用尾插法来将一个结点值为自然数的单链表拆分为两个单链表，其中一个链表保留值为偶数的结点。具体算法如下：

1. 创建两个空链表L1和L2，分别用于存储偶数值结点和奇数值结点。
2. 创建两个指针rear1和rear2，分别指向链表L1和L2的尾结点。
3. 初始化一个计数器counter为1，用于判断结点的奇偶性。
4. 遍历给定的单链表L，从链表头开始循环，直到遍历到链表末尾。
5. 判断当前结点的值是否为偶数，如果是偶数则将其插入链表L1中，否则插入链表L2中。
6. 更新rear1或rear2的指向，将其指向新插入的结点。
7. 更新计数器counter，使其加1。
8. 遍历完整个链表L后，将rear1和rear2的next指针都置为NULL，表示链表结束。
9. 返回拆分得到的两个链表L1和L2。

数据结构，设计一个算法,将一个结点值自然数的单链表拆分为两个单链表,原表中保留值为偶数的

这个算法是为了将一个结点值为自然数的单链表拆分为两个单链表，并且原表中保留值为偶数的结点。首先，我们创建两个新的链表L1和L2，分别用来存储奇数和偶数结点。然后，遍历原链表，对于每一个结点，我们判断其值是奇数还是偶数，如果是奇数，则将其插入到L1中，如果是偶数，则将其插入到L2中。最后，将L1和L2的尾结点的next指针置为NULL，表示链表结束。