单链表的逆置头插法c
时间: 2023-11-09 20:05:25 浏览: 105
单链表的逆置是指将链表中的元素顺序颠倒过来,头插法是一种常用的单链表逆置方法。具体实现方法如下:
1. 定义两个指针p和q,p指向原链表的第一个节点,q用于存储p的下一个节点。
2. 将原链表的头节点的next指针置为NULL,表示新链表的末尾。
3. 循环遍历原链表,每次将p节点插入到新链表的头部,即将p节点的next指针指向新链表的第一个节点,再将新链表的头节点指向p节点。
4. 将q节点赋值给p节点,继续循环遍历原链表,直到p节点为NULL,表示原链表已经遍历完毕。
5. 返回新链表的头节点。
下面是代码实现:
```
typedef struct LinkList {
int data;
struct LinkList* next;
}LinkList;
//单链表的逆置,头插法
LinkList reverseList1(LinkList* L) {
//定义两个指针
LinkList* p, * q;
p = L->next;
L->next = NULL;
while(p != NULL) {
q = p->next;//先存储p的下一个结点,方便进行下一次循环
p->next = L->next;//把p结点的next域指向L的下一个结点
L->next = p;//然后将头结点指向p,就让p成为了首元素
p = q;//将下一个要处理的结点赋给p
}
return L;
}
```
相关问题
c语言就地逆置一条带头节点的单链表,头插法
假设链表的头节点为head,原链表为:head -> a -> b -> c -> d
1. 从头节点的下一个节点a开始,依次将每个节点插入到头节点head之后
2. 需要一个中间变量p来暂存当前节点的下一个节点,防止链表断裂
代码实现如下:
```c
void reverseList(Node *head) {
if (head == NULL || head->next == NULL) {
return;
}
Node *p = head->next; // p指向第一个要插入的节点a
head->next = NULL; // 将头节点的next指针置为空,防止链表断裂
while (p != NULL) {
Node *next = p->next; // 暂存下一个节点
p->next = head->next; // 将p节点插入到头节点之后
head->next = p;
p = next; // p指向下一个节点,继续插入操作
}
}
```
执行上述代码后,链表变为:head -> d -> c -> b -> a
利用尾插法建立单链表,利用头插法完成单链表的逆置并输出逆置后的单链表用c语言实现
好的,下面是用 C 语言实现尾插法建立单链表,利用头插法完成单链表的逆置并输出逆置后的单链表的代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结点
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 尾插法建立链表
ListNode* createList() {
ListNode* head = (ListNode*)malloc(sizeof(ListNode)); // 头结点不存储数据
head->next = NULL;
ListNode* tail = head;
int x;
while (scanf("%d", &x) != EOF) {
ListNode* p = (ListNode*)malloc(sizeof(ListNode));
p->val = x;
p->next = NULL;
tail->next = p;
tail = p;
}
return head->next;
}
// 头插法逆置链表
ListNode* reverseList(ListNode* head) {
ListNode* newHead = NULL;
while (head) {
ListNode* p = head;
head = head->next;
p->next = newHead;
newHead = p;
}
return newHead;
}
// 输出链表
void printList(ListNode* head) {
while (head) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
ListNode* head = createList();
head = reverseList(head);
printList(head);
return 0;
}
```
希望这个 C 语言的实现对你有所帮助!