采用单链表存储的线性表A(A带表头结点head)的数据元素逆置算法
时间: 2023-04-10 11:04:52 浏览: 118
可以使用头插法,从原链表的第二个节点开始,依次将节点插入到头结点之后,直到原链表的最后一个节点。具体实现可以参考以下代码:
```
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* p = head->next;
head->next = NULL;
while (p != NULL) {
ListNode* q = p->next;
p->next = head->next;
head->next = p;
p = q;
}
}
```
其中,ListNode 是链表节点的结构体,包含一个指向下一个节点的指针 next。
相关问题
写出一个采用单链表存储的线性表A(A带表头结点Head)的数据元素逆置的算法)
可以使用三个指针分别指向当前节点、前一个节点和后一个节点,依次遍历链表并将当前节点的指针指向前一个节点,直到遍历完整个链表。具体实现如下:
```
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* prev = NULL;
ListNode* curr = head->next;
ListNode* next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = prev;
}
```
其中,ListNode 是链表节点的结构体,包含一个 val 值和一个指向下一个节点的指针 next。
试写出一个采用单链表存储的线性表A(A带表头结点Head)的数据元素逆置的算法。
可以使用头插法实现单链表的逆置,具体算法如下:
1. 定义三个指针变量p、q、r,分别指向头结点、第一个结点和第二个结点。
2. 将p指向头结点,q指向第一个结点,r指向第二个结点。
3. 将q的next指针指向p,即将第一个结点插入到头结点之后。
4. 将p、q、r依次向后移动一个结点,即p指向q,q指向r,r指向r的next。
5. 重复步骤3和4,直到r指向空结点,此时单链表逆置完成。
下面是具体的代码实现:
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* p = head;
ListNode* q = head->next;
ListNode* 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;
}
阅读全文