leetcode328. Odd Even Linked List

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

You must solve the problem in O(1) extra space complexity and O(n) time complexity.

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

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

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

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

class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:

        f_p1 = None
        pointer1 = head
        pointer2 = head
        counter = 1

        if head == None or head.next == None:  # 特殊情况
            return head

        while pointer1.next != None:  # 找到最后就不找了
            f_p1 = pointer1
            pointer1 = pointer1.next
            counter += 1

            if counter % 2 == 1 and counter > 1:  # 开始移动
                f_p1.next = pointer1.next

                pointer1.next = pointer2.next
                pointer2.next = pointer1

                pointer2 = pointer2.next  # pointer2往后移动一格
                f_p1, pointer1 = pointer1, f_p1  # 顺序变了我们重新纠正过来。

            # 下面这段代码可以帮助查看所有的步骤过程。
            # str1 = ""
            # test = head
            # while test != None:
            #     str1 += "->" + str(test.val)
            #     test = test.next
            # print(str1, "|  f_p1:", f_p1.val, "|  p1:", pointer1.val, "|  p2:", pointer2.val, "|  counter:", counter)
        return head