1075 链表元素分类 (25 分)
时间: 2023-04-25 22:05:59 浏览: 157
这道题目要求我们将一个链表中的元素按照奇偶性分成两个链表,其中奇数链表中的元素顺序与原链表中的顺序相同,偶数链表中的元素顺序与原链表中的顺序相反。
我们可以使用两个指针分别指向奇数链表和偶数链表的尾部,然后遍历原链表,将奇数节点插入奇数链表的尾部,偶数节点插入偶数链表的头部。最后将偶数链表反转即可。
具体实现可以参考以下代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* createList(vector<int>& nums) {
ListNode* head = new ListNode(0);
ListNode* p = head;
for (int num : nums) {
p->next = new ListNode(num);
p = p->next;
}
return head->next;
}
void printList(ListNode* head) {
while (head) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* oddTail = head;
ListNode* evenHead = head->next;
ListNode* evenTail = evenHead;
while (evenTail && evenTail->next) {
oddTail->next = evenTail->next;
oddTail = oddTail->next;
evenTail->next = oddTail->next;
evenTail = evenTail->next;
}
oddTail->next = evenHead;
ListNode* p = evenHead;
ListNode* q = NULL;
while (p) {
ListNode* tmp = p->next;
p->next = q;
q = p;
p = tmp;
}
evenHead = q;
oddTail->next = evenHead;
return head;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
ListNode* head = createList(nums);
printList(head);
head = oddEvenList(head);
printList(head);
return 0;
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)