本文共 1348 字，大约阅读时间需要 4 分钟。

为了解决将链表中的奇数节点和偶数节点分别排列在一起的问题，我们使用双指针的方法来重新排列链表。这种方法在原地完成，确保了时间复杂度为O(nodes)，空间复杂度为O(1)。

方法思路

我们使用两个链表来分别存储奇数节点和偶数节点。遍历原链表时，遇到奇数节点则将其添加到奇数链表尾部，遇到偶数节点则添加到偶数链表尾部。处理完成后，将奇数链表尾部的下一个指针指向偶数链表头部，并将偶数链表尾部的下一个指针指向null。

解决代码

class ListNode:    def __init__(self, val=0, next=None):        self.val = val        self.next = nextdef oddEvenList(self, head: ListNode) -> ListNode:    if not head or not head.next:        return head        odd_head = None    odd_tail = None    even_head = None    even_tail = None        curr = head    while curr:        next_node = curr.next        if curr.val % 2 == 1:  # 处理奇数节点            if not odd_head:                odd_head = odd_tail = curr            else:                odd_tail.next = curr                odd_tail = curr        else:  # 处理偶数节点            if not even_head:                even_head = even_tail = curr            else:                even_tail.next = curr                even_tail = curr        curr = next_node        # 将奇数链表尾的下一个指向偶数链表头    if odd_tail:        odd_tail.next = even_head    # 偶数链表尾的下一个指向null    if even_tail:        even_tail.next = None        return head

代码解释

这种方法确保了我们能够在原地完成链表的重排，满足了时间和空间复杂度的要求。

转载地址：http://jhba.baihongyu.com/