奇偶链表

给定单链表的头节点 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=head
        second.next=head.next

        # 变量存储偶数链表的头节点
        even = second.next
           
        # 定义一个变量curr指向头节点
        curr=head
        
        # 这里是为了后面对奇偶位置做区分
        count=0
        while curr:
            count+=1
            # 如果是奇数
            if count%2==1:
                first.next=curr
                first = first.next
            # 如果是偶数
            elif count%2==0:
                second.next=curr
                second = second.next
            curr=curr.next
        
        # 偶数链表尾节点没有指向null
        second.next=None
        
        # 对奇数链表和偶数链表做拼接
        first.next=even
        return 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=even

        while even and even.next:
            odd.next=even.next
            odd=odd.next

            even.next=odd.next
            even=even.next
        
        # 连接两个链表
        odd.next=even_head
        return head