题目

给定单链表的头节点 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