题目

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点别离组合在一起，而后返回从新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请留神，偶数组和奇数组外部的绝对程序应该与输出时保持一致。

你必须在 O(1) 的额定空间复杂度和 O(n) 的工夫复杂度下解决这个问题。

输出: head = [1,2,3,4,5]输入: [1,3,5,2,4]输出: head = [2,1,3,5,6,4,7]输入: [2,3,6,7,1,5,4]

思路

定义4个指针
2个指针负责偶数节点链表
2个指针负责奇数节点链表
其中，1个指针负责定位各自的头节点，1个指针负责挪动批改各自的其余节点的next指向
最初将批改好的奇数节点链表的尾 和 偶数节点链表的头连接起来

def oddEvenList(self, head: ListNode) -> ListNode:    if head==None or head.next==None:        return head    # 奇数节点挪动指针    odd = head    # 奇数节拍板指针    oddHead = head    # 偶数节点挪动指针    even = head.next    # 偶数节拍板指针    evenHead = head.next        # 当奇数挪动指针，为None，或者它的next指向None，意味着遍历完结    # 为什么是依据奇数挪动指针来判断的？    # 因为题目规定，链表的第一个节点是奇数节点    # 那么整个链表的奇数节点个数，肯定是要么等于偶数节点个数，要么比偶数节点多1个    # 即 奇-偶-奇 或者 奇-偶-奇-偶    # 所以要抉择较多的那一个作为判断循环完结的条件    # 如果抉择偶数的话，奇-偶-奇，第一次循环 奇-偶 第二次循环 奇-None，就出错了    while even and even.next:        odd.next = even.next        odd = odd.next        even.next = odd.next        even = even.next    odd.next = evenHead    return oddHead