设有一带头结点的单链表,编程将链表颠倒过来，即（a1...an）逆置为(an...a1)，要求不用另外的数组或结点完成.

可以回答这个问题。可以使用三个指针，分别指向当前结点、前一个结点和后一个结点，依次将当前结点的 next 指针指向前一个结点，然后将三个指针向后移动一个结点，直到当前结点为 NULL，最后将头结点指向逆置后的链表的第一个结点。

相关问题

已知带头结点的单链表L={a1,a2,...an}，试编写一个算法，将L中的元素进行逆置，即L ={an,an-1,...a1}

以下是基于Python语言的算法实现：

def reverse_linked_list(head):
    """
    将带头结点的单链表逆置
    """
    if head is None or head.next is None:
        return head
    pre_node = None
    cur_node = head.next
    while cur_node is not None:
        next_node = cur_node.next
        cur_node.next = pre_node
        pre_node = cur_node
        cur_node = next_node
    head.next = pre_node
    return head

算法思路：

1. 首先判断链表是否为空或只有一个节点，如果是，则直接返回原链表头结点；
2. 初始化前驱节点 pre_node 为 None，当前节点 cur_node 为头结点的下一个节点（即第一个节点）；
3. 遍历链表，将当前节点的下一个节点保存为 next_node；
4. 将当前节点的 next 指针指向前驱节点 pre_node；
5. 将前驱节点 pre_node 更新为当前节点 cur_node；
6. 将当前节点 cur_node 更新为下一个节点 next_node；
7. 遍历完成后，将头结点的 next 指针指向逆置后的链表头节点 pre_node；
8. 返回头结点。

这样就可以将链表逆置。

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;
}