3.编写算法逆置一个带头结点的双链表。

1. 判断双链表是否为空，如果为空则直接返回头结点
2. 初始化3个指针pre、p、q，分别指向头结点、第一个节点、第二个节点
3. 将pre的next指向NULL，p的next指向NULL，p的prev指向NULL
4. 循环遍历链表，直到q指向NULL
5. 将p的prev指向q，q的next指向p，p、q向前移动一个节点
6. 将p的next指向pre，pre的prev指向p，pre向前移动一个节点
7. 将头结点的next指向pre，pre的prev指向头结点
8. 返回头结点

算法实现如下：

void reverseList(DLinkedList head)
{
    if(head == NULL || head->next == NULL)
        return;
    
    DLinkedList pre = head, p = pre->next, q = p->next;
    pre->next = NULL;
    p->prev = NULL;
    
    while(q != NULL)
    {
        p->next = pre;
        pre->prev = p;
        pre = p;
        p = q;
        q = q->next;
    }
    
    p->next = pre;
    pre->prev = p;
    head->next = p;
    p->prev = head;
}

相关问题

编写算法逆置一个带头结点的双链表

算法步骤如下：

1. 如果链表为空或者只有一个节点，则直接返回原链表。
2. 定义三个指针p、q、r，分别指向头结点、第一个节点、第二个节点。
3. 将第一个节点的前驱指针和后继指针都置为空，作为逆置后的最后一个节点。
4. 依次将q节点的后继指向p节点，p节点的前驱指向q节点，r节点的前驱指向q节点，q节点的后继指向r节点。
5. 将p指针指向q节点，q指针指向r节点，r指针指向r节点的后继节点。
6. 如果r指针不为空，则重复执行步骤4和步骤5，直到r指针为空为止。
7. 将头结点的前驱指针置为空，将逆置后的最后一个节点的后继指针指向头结点，将头结点的后继指针指向逆置后的第一个节点。
8. 返回逆置后的链表。

以下是算法的C++实现代码：

struct ListNode {
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x) : val(x), prev(NULL), next(NULL) {}
};

ListNode* reverseList(ListNode* head) {
    if (!head || !head->next) {
        return head;
    }
    ListNode *p = head, *q = head->next, *r = q->next;
    p->next = NULL;
    while (r) {
        q->next = p;
        p->prev = q;
        r->prev = q;
        p = q;
        q = r;
        r = r->next;
    }
    q->next = p;
    p->prev = q;
    head->prev = NULL;
    head->next = q;
    return head;
}

编写算法逆置一个带头结点的双链表。

1. 定义一个指针p指向链表的最后一个结点。
2. 从最后一个结点开始，依次遍历链表，将每个结点的前驱结点和后继结点交换。
3. 遍历到头结点时，将头结点的前驱结点置为空，头结点的后继结点作为新的头结点。
4. 返回逆置后的链表头结点。

伪代码如下：

reverseList(head):
if head is null or head.next is null:
return head
p = head.next.prev
while p is not null:
temp = p.prev
p.prev = p.next
p.next = temp
p = p.prev
head.prev = null
head = head.next
head.prev.next = null
head.prev = null
return head