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]
提示:
n ==链表中的节点数
0 <= n <= 104
106<= Node.val <= 106
通过次数157,491提交次数240,948
法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: Optional[ListNode]) -> Optional[ListNode]: if head is None or head.next is None: return head odd_head, even_head = ListNode(-1), ListNode(-1) odd_tail, even_tail = odd_head, even_head cur = head while cur and cur.next: # 先保存好下一组 nxt = cur.next.next # 分别连接好，且向后移动 odd_tail.next = cur even_tail.next = cur.next odd_tail = odd_tail.next even_tail = even_tail.next # 将后面的断开 odd_tail.next = None even_tail.next = None # 开始下一组 cur = nxt # 将单个接上去 if cur: odd_tail.next = cur odd_tail = odd_tail.next # 奇偶合并 odd_tail.next = even_head.next return odd_head.next