设计一个算法,将一个带头结点的单链表拆分为两个表,原表中保留结点值为偶数的结点,而结点值为奇数的结点按它们在原表中的相对次序组成一个新表。
时间: 2023-04-10 13:03:43 浏览: 121
可以使用两个指针分别指向原链表的头结点和新链表的头结点,遍历原链表,将偶数结点插入原链表中,将奇数结点插入新链表中。具体实现如下:
```
ListNode* splitList(ListNode* head) {
ListNode* evenHead = new ListNode(0); // 偶数结点的头结点
ListNode* oddHead = new ListNode(0); // 奇数结点的头结点
ListNode* evenTail = evenHead; // 偶数结点的尾结点
ListNode* oddTail = oddHead; // 奇数结点的尾结点
ListNode* p = head->next; // 当前结点
while (p != nullptr) {
if (p->val % 2 == 0) { // 偶数结点
evenTail->next = p;
evenTail = p;
} else { // 奇数结点
oddTail->next = p;
oddTail = p;
}
p = p->next;
}
evenTail->next = nullptr; // 偶数结点的尾结点指向空
oddTail->next = nullptr; // 奇数结点的尾结点指向空
head->next = evenHead->next; // 原链表的头结点指向偶数结点的头结点
delete evenHead; // 释放偶数结点的头结点
return oddHead; // 返回奇数结点的头结点
}
```
这个算法的时间复杂度为 O(n),空间复杂度为 O(1)。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)