带表头结点单链表的逆置
时间: 2024-03-23 15:32:19 浏览: 12
对于带头结点的单链表,我们可以从头结点的下一个节点开始,依次将每个节点插入到头结点之后,直到所有节点都被插入完成,最后再将头结点的next指针指向新的第一个节点即可。
具体实现如下:
```c++
void reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* p = head->next;
ListNode* q = p->next;
while (q != nullptr) {
p->next = q->next;
q->next = head->next;
head->next = q;
q = p->next;
}
}
```
相关问题
用C语言实现带表头结点单链表的逆置和排序运算
好的,这是一个关于C语言实现带表头结点单链表的逆置和排序运算的问题。对于逆置操作,可以使用三个指针来实现:pre指针、cur指针和next指针。每次将cur指针指向的节点的后继指针指向pre指针指向的节点,然后将三个指针都向后移动一个节点。当cur指针移动到最后一个节点时,将头结点的后继指针指向cur指针指向的节点即可。
对于排序操作,可以使用冒泡排序和快速排序两种方法。冒泡排序的基本思路是每次比较相邻的两个元素,如果不符合排序规则,则交换它们的位置;而快速排序是利用分治的思想,将一个大问题分解为若干个小问题来解决。具体实现过程可以通过递归的方式来完成。
以上是我对于你的问题的回答,希望对你有所帮助。
用C语言写出带表头结点单链表的逆置和排序运算的代码
好的,以下是用C语言实现带表头结点单链表的逆置和排序运算的代码:
```
#include <stdio.h>
#include <stdlib.h>
/* 定义链表节点结构体 */
typedef struct Node
{
int data; // 数据域
struct Node *next; // 指针域
} Node;
/* 创建带表头结点的单链表 */
Node *createLinkedList(int n)
{
Node *head = (Node *)malloc(sizeof(Node));
head->next = NULL;
Node *p = head;
int i;
for (i = 0; i < n; i++)
{
Node *node = (Node *)malloc(sizeof(Node));
printf("请输入第%d个节点的数据:", i + 1);
scanf("%d", &node->data);
node->next = NULL;
p->next = node;
p = node;
}
return head;
}
/* 输出单链表 */
void printLinkedList(Node *head)
{
Node *p = head->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
/* 单链表逆置 */
void reverseLinkedList(Node *head)
{
Node *p = head->next;
head->next = NULL;
while (p != NULL)
{
Node *tmp = p;
p = p->next;
tmp->next = head->next;
head->next = tmp;
}
}
/* 单链表排序 */
void sortLinkedList(Node *head)
{
Node *p, *q;
int tmp;
for (p = head->next; p != NULL; p = p->next)
{
for (q = p->next; q != NULL; q = q->next)
{
if (p->data > q->data)
{
tmp = p->data;
p->data = q->data;
q->data = tmp;
}
}
}
}
int main()
{
int n;
printf("请输入链表长度:");
scanf("%d", &n);
Node *head = createLinkedList(n);
printf("原始链表:");
printLinkedList(head);
reverseLinkedList(head);
printf("逆置后的链表:");
printLinkedList(head);
sortLinkedList(head);
printf("排序后的链表:");
printLinkedList(head);
return 0;
}
```
以上代码实现了带表头结点单链表的逆置和排序运算。输入链表长度和各个节点的数据,然后输出原始链表、逆置后的链表和排序后的链表。