328. 奇偶链表 · Algorithm Lab

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

提示:

n == 链表中的节点数
0 <= n <= 104
-106 <= Node.val <= 106

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def oddEvenList(self, head):
        if not head or not head.next: # 如果只有一个节点或为空
            return head
        
        pre_odd = ListNode(0)  # 奇数节点前驱
        pre_even = ListNode(0)  # 偶数节点前驱
        odd = pre_odd  # 奇数移动指针
        even = pre_even  # 偶数移动指针
        is_odd = True  # 是否为奇数位置
        while head:
            if is_odd:
                odd.next = head
                odd = odd.next
            else:
                even.next = head
                even = even.next
            is_odd = not is_odd  # 切换奇偶标记
            head = head.next
        even.next = None
        odd.next = pre_even.next
        return pre_odd.next
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """