链表中的经典问题——奇偶链表
奇偶链表
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
题解一，双指针：
这是一个比较拉跨的代码，看着可能比较冗长，这是我第一次的时候写出来的，当时我觉得的整体思路上还算比较清晰
class Solution:def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:# 如果head为空，或head.next为空if not head or not head.next:return head# 使用双指针的方法，随便定义两个节点first = ListNode(0)second = ListNode(1)# 将它们分别指向头节点和头节点的下一个节点first.next=headsecond.next=head.next# 变量存储偶数链表的头节点even = second.next# 定义一个变量curr指向头节点curr=head# 这里是为了后面对奇偶位置做区分count=0while curr:count+=1# 如果是奇数if count%2==1:first.next=currfirst = first.next# 如果是偶数elif count%2==0:second.next=currsecond = second.nextcurr=curr.next# 偶数链表尾节点没有指向nullsecond.next=None# 对奇数链表和偶数链表做拼接first.next=evenreturn head题解二，双指针（简化版）：
class Solution:def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:# 如果head或head.next是空，则返回head本身if head is None or head.next is None:return head# 定义变量odd指向head引用，即odd和head指向同一节点odd=head# 定义变量even指向head.next引用even=head.next# 保存even的头节点even_head=evenwhile even and even.next:odd.next=even.nextodd=odd.nexteven.next=odd.nexteven=even.next# 连接两个链表odd.next=even_headreturn head