一个有n个节点的双向循环链表H，随机存放奇数和偶数，试设计一高效算法实现链表结点中的奇偶数相邻存放（不要求有序），多余的奇数和偶数放在最后

可以使用双指针法实现奇偶数相邻存放。具体实现方法如下：

1. 定义两个指针odd和even，分别指向链表中第一个奇数结点和第一个偶数结点；
2. 遍历链表，如果当前结点的值为奇数，则将其插入到odd指针所指结点的后面，并将odd指针后移；如果当前结点的值为偶数，则将其插入到even指针所指结点的后面，并将even指针后移；
3. 遍历完链表后，将odd指针所指结点的后继指针指向even指针所指结点的后继指针，将even指针所指结点的后继指针指向NULL，这样就将奇偶数相邻存放，并将多余的奇数和偶数放在最后。

下面是具体的实现代码：

void rearrangeList(ListNode *head) {
    if (head == NULL) return;
    ListNode *odd = head, *even = head->next, *evenHead = even;

    while (even != NULL && even->next != NULL) {
        odd->next = even->next;
        odd = odd->next;
        even->next = odd->next;
        even = even->next;
    }

    odd->next = evenHead;

}

时间复杂度为O(n)，空间复杂度为O(1)，是一种高效的算法实现方式。

相关问题

一个有n个结点的双向循环链表H，随机存放奇数和偶数，试设计一高效算法实现链表节点中奇偶数相邻存放（不要求有序），多余的奇数和偶数放在最后。

可以使用两个指针分别从头尾开始遍历链表，当两个指针指向的节点不符合要求时，交换它们的值。具体做法如下：

1. 定义两个指针 p 和 q，分别指向链表的头和尾。
2. 当 p 和 q 指向的节点都是奇数或者都是偶数时，p 向后移动一位，直到 p 指向一个奇数节点和 q 指向一个偶数节点。
3. 当 p 和 q 指向的节点不符合要求时，交换它们的值，然后 p 向后移动一位，q 向前移动一位。
4. 重复步骤 2 和步骤 3，直到 p 和 q 相遇为止。

最后，p 和 q 相遇的位置就是链表中奇偶数相邻存放的位置。接下来，只需要将 p 之后的所有奇数节点和 q 之前的所有偶数节点交换位置即可。

下面是算法的示意图和Python实现代码：

def reorder_list(head):
    if not head:
        return None
    
    p, q = head, head.prev
    while p != q and p.prev != q:
        if p.val % 2 == q.val % 2:
            p = p.next
        else:
            p.val, q.val = q.val, p.val
            p = p.next
            q = q.prev
    
    # 将多余的奇数和偶数节点移到链表尾部
    tail = p if p == q else p.prev
    while tail.val % 2 == 0:
        tail = tail.prev
    
    curr = head
    while curr != tail:
        if curr.val % 2 == 0:
            curr.val, tail.val = tail.val, curr.val
            while tail.val % 2 == 0:
                tail = tail.prev
        curr = curr.next
    
    return head

其中，head 表示链表的头节点，每个节点包含三个属性：val 表示节点的值，next 表示指向下一个节点的指针，prev 表示指向上一个节点的指针。函数的返回值是排序后的链表头节点。

有一个带头结点的双链表L，其所有元素均为整数，设计一个算法删除所有奇数元素的节点

可以遍历整个双链表，对于每个节点，判断其存储的整数是否为奇数，如果是，则删除该节点。

具体实现过程如下：

1. 定义指针p指向双链表的第一个节点（即头结点的下一个节点）。
2. 遍历双链表，对于每个节点执行以下操作：
- 如果该节点存储的整数为奇数，则将该节点从双链表中删除。
- 否则，将指针p指向下一个节点。
3. 遍历完成后，返回删除奇数节点后的双链表。

代码实现如下（假设双链表的节点结构体为Node，包含prev、next和value三个成员变量）：

def remove_odd_nodes(L):
    p = L.next
    while p:
        if p.value % 2 == 1:
            p.prev.next = p.next
            if p.next:
                p.next.prev = p.prev
        else:
            p = p.next
    return L

其中，L表示双链表的头结点。注意，在删除节点时，需要同时修改该节点的前驱节点和后继节点的指针，以保证双链表的正确性。