328. 奇偶链表

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

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

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

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

示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

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

---

直接一次遍历

将偶数节点放到新链表，结束后链接到旧链表之后

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        odd_dummy = ListNode(next=head)
        even_dummy = ListNode()
        even_tail = even_dummy
        p = head
        pre = odd_dummy
        count = 1
        while p:
            if count % 2 == 1:
                pre = p
                p = p.next
            else:
                even_tail.next = p
                even_tail = p
                pre.next = p.next
                p = p.next
            count += 1
        even_tail.next = None
        pre.next = even_dummy.next

        return odd_dummy.next