标签: 链表
难度: Medium
给定单链表的头节点 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运行时间: 56 ms
内存: 16.9 MB
# 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:
dummy_left = ListNode(next=head)
dummy_right = ListNode()
p = dummy_right
pre = dummy_left
cur = head
odd = True
while cur:
if odd:
pre = pre.next
odd = False
else:
pre.next = cur.next
cur.next = None
p.next = cur
p = p.next
odd = True
cur = pre.next
pre.next = dummy_right.next
return dummy_left.next
本题解的思路是通过维护两个指针，分别指向奇数位置和偶数位置的节点，然后将偶数位置的节点逐个摘除并接到另一个链表上。最后，将两个链表连接起来。这样可以在一次遍历中完成奇偶分离。
时间复杂度: O(n)
空间复杂度: O(1)
# 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:
dummy_left = ListNode(next=head) # 创建一个假的头节点，方便处理边界情况
dummy_right = ListNode() # 创建一个用于存放偶数节点的链表
p = dummy_right
pre = dummy_left
cur = head
odd = True
while cur:
if odd:
pre = pre.next # 如果是奇数位置，向前移动
odd = False
else:
pre.next = cur.next # 如果是偶数位置，将当前节点摘除并接到偶数链表上
cur.next = None
p.next = cur
p = p.next
odd = True
cur = pre.next
pre.next = dummy_right.next # 将偶数链表接到奇数链表的末尾
return dummy_left.next # 返回真正的头节点
`dummy_left`节点作为假的头节点，主要用于简化对链表头部的处理，尤其是在头部节点也可能被操作或变更时，可以避免复杂的边界条件判断。通过始终通过`dummy_left.next`来访问真正的头节点，即使头节点变化，也不需要额外的判断或更新。`dummy_right`则用于临时存储被摘除的偶数位置节点，它同样作为一个假的头节点，帮助轻松地在其后添加节点，并在处理完毕后容易地获取新的偶数节点链表的头部。
在将偶数位置的节点`cur`移动到偶数链表中时，需要将`cur.next`设置为`None`以断开原来的连接，防止新的偶数链表与原链表形成环或其他不正常的链接。这一步是必要的，因为接下来`cur`将会被接到`dummy_right`表示的偶数链表的末尾。这一操作不会影响原链表的完整性，因为在摘除`cur`节点之前，已经将`cur`的前一个节点`pre`的`next`指向`cur.next`，即跳过了`cur`，保持了链表其余部分的连续性。
实际上，检查`dummy_right.next`是否为`None`是一个好习惯，因为如果原链表全部是奇数节点，那么`dummy_right.next`将会是`None`，直接连接会导致奇数链表的末尾接上一个空节点。虽然在给定的代码中没有这一检查，但最好在连接前添加这样的判断以避免不必要的空节点引用。若不检查，不会造成断链，但会有不必要的空引用。
`odd`变量确实用于控制当前节点是奇数还是偶数位置，通过在每次循环中交替其值来实现。这种方法本质上是稳定的，因为它依赖于节点的遍历顺序，而与链表的总长度奇偶性无关。无论链表的长度是奇数还是偶数，`odd`的初始值和其在循环中的变化逻辑确保了节点正确地被识别为奇数位置或偶数位置。因此，这种方法不会因为链表长度的奇偶性不同而导致错误的分离。