给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为O(nodes),nodes 为节点总数。
时间: 2024-05-25 19:19:36 浏览: 65
数据结构与算法 c++实现 两个单链表合并为一个单链表,两个表的元素交错排列,新表用原表结点的内存空间 按元素序列的奇偶分割单
5星 · 资源好评率100%
好的,这是一道链表操作的题目。我们可以使用两个指针odd和even来分别指向奇数节点和偶数节点的头部,然后将奇数节点和偶数节点分别串联起来。具体的实现方式可以参考如下的代码:
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next || !head->next->next) {
return head;
}
ListNode* odd = head;
ListNode* even = head->next;
ListNode* temp = even;
while (even && even->next) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = temp;
return head;
}
};
这个算法的时间复杂度是O(n),空间复杂度是O(1)。需要注意的是题目中的奇偶指的是节点的编号而不是节点的值,因此我们需要根据节点的位置来进行交替操作。
阅读全文