裸睡，一觉醒来发现隔壁躺着hr~
P
虎哥约 4 分钟
虎哥约 4 分钟算法题：奇偶链表
思路
两个链表：我们可以创建两个新的链表，一个链表专门用来存放奇数位置的节点，另一个用来存放偶数位置的节点。 遍历原链表：遍历链表的过程中，每遇到一个奇数位置的节点就把它加到奇链表里，偶数位置的节点就加到偶链表里。 连接奇偶链表：当遍历完所有节点后，我们将奇链表和偶链表连接起来。这样，奇链表的头节点会指向偶链表的头节点，最终返回新的链表头。
代码实现
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = nextdef oddEvenList(head):
if not head or not head.next:
return headodd = head # 奇数链表的头节点
even = head.next # 偶数链表的头节点
even_head = even # 记录偶数链表的头节点，最后需要将奇数链表接上while even and even.next:
odd.next = odd.next.next # 跳过偶数节点，指向下一个奇数节点
even.next = even.next.next # 跳过奇数节点，指向下一个偶数节点
odd = odd.next # 移动到下一个奇数节点
even = even.next # 移动到下一个偶数节点odd.next = even_head # 将奇数链表连接到偶数链表的头节点
return head # 返回新的链表头节点
解释一下代码
初始化奇偶链表：我们首先通过 odd = head和even = head.next初始化两个链表。odd指向链表中的第一个节点，even指向第二个节点。这个步骤确保了奇偶链表从头开始分别构建。遍历链表：然后，利用 while even and even.next来遍历原链表。even和odd一步一步向后跳，确保每次odd指向一个奇数位置的节点，even指向一个偶数位置的节点。链表连接：最后， odd.next = even_head这一步是关键。它把奇链表和偶链表连接起来，完成整个奇偶链表的重排。
性能分析
时间复杂度：O(n)，我们只遍历了一遍链表，因此时间复杂度是线性的。 空间复杂度：O(1)，我们只使用了常数空间来存储指针，并没有额外使用任何数据结构，所以空间复杂度是常数级别。
奇偶链表这个题目，不算特别复杂，但却非常典型，能锻炼我们对链表的理解和操作。通过这个题目，你可以更好地掌握链表的操作技巧，比如如何通过指针的操作调整节点顺序等。
只要我们掌握了这些操作，以后在面对复杂的链表题时就会更加得心应手。
对编程、职场感兴趣的同学，大家可以联系我微信：golang404，拉你进入“程序员交流群”。
虎哥作为一名老码农，整理了全网最全《python高级架构师资料合集》。