设计一个算法,将带头结点的单链表逆置
时间: 2023-06-05 11:48:13 浏览: 357
借助栈将一个带头结点的单链表倒置
4星 · 用户满意度95%
算法步骤如下:
1. 定义三个指针:p、q、r,分别指向头结点、第一个结点和第二个结点。
2. 将p的next指针指向NULL,表示逆置后的链表的尾结点。
3. 循环遍历链表,每次将q的next指针指向p,表示将当前结点逆置。
4. 将p、q、r指针向后移动一个结点,继续遍历链表。
5. 当r指针指向NULL时,表示遍历完整个链表,逆置完成。
6. 将头结点的next指针指向q,表示逆置后的链表的头结点。
具体实现可以参考以下代码:
void reverseList(Node* head) {
Node *p = head, *q = head->next, *r = q->next;
p->next = NULL;
while (r != NULL) {
q->next = p;
p = q;
q = r;
r = r->next;
}
q->next = p;
head->next = q;
}
阅读全文