给定一个链表，对链表进行分隔，使得所有奇数都在单链表的左边，所有偶数都在单链表的右边。 //应当保留两个分区中每个结点的初始相对位置。示例：输入: head = 1->4->3->2->5->8。输出: 1->3->5->4->2->8。

好的，这是一道链表的题目，我会尽力回答你的问题。

首先，我们可以创建两个新链表，一个用于存放奇数结点，一个用于存放偶数结点。然后，我们遍历原链表，将奇数结点添加到奇数链表中，将偶数结点添加到偶数链表中。

最后，我们将奇数链表的尾结点指向偶数链表的头结点，这样就能保留两个分区中每个结点的初始相对位置。以下是具体的实现过程：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def oddEvenList(head: ListNode) -> ListNode:
    if not head:
        return head

    odd = head
    even = head.next
    even_head = even

    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next

    odd.next = even_head

    return head

这段代码的时间复杂度为 $O(n)$，其中 $n$ 是链表中结点的个数。

相关问题

给定一个链表，对链表进行分隔，使得所有奇数都在单链表的左边，所有偶数都在单链表的右边。应当保留两个分区中每个结点的初始相对位置。

可以使用两个指针odd和even分别指向奇数节点和偶数节点的头结点，然后遍历链表，将奇数节点接在odd后面，偶数节点接在even后面，最后将odd的尾部指向even的头部即可。

具体实现可以按照以下步骤进行：

1. 初始化指针odd和even分别指向奇数节点和偶数节点的头结点。

2. 遍历链表，对于每个节点，判断其奇偶性。

3. 如果是奇数节点，将其接在odd的后面，并更新odd指针。

4. 如果是偶数节点，将其接在even的后面，并更新even指针。

5. 遍历结束后，将odd的尾部指向even的头部。

代码实现如下：

ListNode* oddEvenList(ListNode* head) {
    if (!head || !head->next) return head; // 特判空链表和只有一个节点的链表
    ListNode *odd = head, *even = head->next, *evenHead = even;
    while (even && even->next) {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }
    odd->next = evenHead;
    return head;
}

时间复杂度为O(n)，其中n是链表的长度。空间复杂度为O(1)。