1 题目
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
2 解析
（1）方法一
插入排序的思想，四个指针，
- prev：奇数的链表插入位置
- curr，奇数位置
- mid:偶数位置
- end：记录奇数位置后续的链表尾巴
注意：要判断【】、【1】两种类型的链表，是不做处理，直接返回
（2）方法二
插入排序的思想，三个指针，
- p：奇数的链表插入位置
- q:偶数位置
- r:奇数位置
注意：要判断空的链表不做处理
3 python实现
（1）方法一
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]: # 插入排序的思想，四个指针，prev：奇数的链表插入位置，curr，奇数位置，mid:偶数位置，end：记录奇数位置后续的链表尾巴 # 注意：3个元素以下，直接返回链表 if not head or not head.next : return head prev = head mid =head.next curr = head.next.next while curr : # 记录后续节点 end =curr.next # 将奇数节点向前插入 curr.next = prev.next prev.next = curr # 链接后续节点，恢复整个完整链表 mid.next = end # 所有指针往后移动 mid =mid.next prev = prev.next # 注意：可能没有了后续节点 if end: # curr指针移动两步，跳过偶数节点 curr = end.next else: curr = None return head
（2）方法二
三个指针，插入排序的思想 def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]: if not head: return head p,q = head,head.next while q and q.next: r = q.next # 将r后续链表连接上 q.next =r.next # 将r节点前插 r.next = p.next p.next = r p = p.next q = q.next return head
