admin管理员组

文章数量:1122855

链表

文章目录

• 前言
• 一、链表的动态创建
• 二、反转链表
• • 1.三指针迭代法
  • 2.使用头插法建立新链表
• 三、删除链表的倒数第K个结点
• • 1.遍历链表，求出倒数第K个结点
  • 2.快慢指针法进行删除
• 四、合并两个有序链表
• 总结

---

前言

关于五月考核前三题
1.反转链表
2.删除链表的倒数第n个结点
3.合并两个有序链表

---

先进行链表的动态创建

一、链表的动态创建

注意包含头文件<stdlib.h>

//先创建一个结构体
struct Node {int data;struct Node* next;
};
//创建表头
struct Node* CreatList() {struct Node* HeadNode = (struct Node*)malloc(sizeof(struct Node));HeadNode->data = 1;HeadNode->next = NULL;return HeadNode;
}
//创建结点
struct Node* CreatNode(int data) {struct Node* NewNode = (struct Node*)malloc(sizeof(struct Node));NewNode->data = data;NewNode->next = NULL;return NewNode;
}
//链表的头插法
void InserNodeByHead(struct Node* HeadNode, int data) {struct Node* NewNode = CreatNode(data);NewNode->next = HeadNode->next;HeadNode->next = NewNode;
}
//链表的打印
void Print(struct Node* HeadNode) {while (HeadNode->next) {printf("%d ", HeadNode->next->data);HeadNode = HeadNode->next;}printf("\n");
}
//创建一个动态链表
int main() {struct Node* HeadNode = CreatList();int i = 0;//i为循环变量int l = 0;//l为要生成的新链表的长度scanf("%d",  &l);for (i = 0; i < l; i++) {int data = 0;scanf("%d",  &data);InserNodeByHead(HeadNode, data);//利用头插法的循环创建动态链表}Print(HeadNode);
}

二、反转链表

1.三指针迭代法

void ReverseList(struct Node* HeadNode) {struct Node* p = HeadNode->next;struct Node* q = p->next;struct Node* temp = NULL;//经典的三指针联动//依次迭代p->next = NULL;while (q) {temp = q;q = temp->next;temp->next = p;p = temp;}HeadNode->next = temp;
}

将反转函数加入函数体后，运行起来得到这样的结果

2.使用头插法建立新链表

struct Node* ReverseList(struct Node* HeadNode) {struct Node* NewList = CreatList();//创建一个新的链表用来保存反转后的结果struct Node* NewHead = NewList;//记录新链表的头while (HeadNode->next) {int data = HeadNode->next->data;HeadNode = HeadNode->next;InserNodeByHead(NewList, data);//通过头插法把原链表中的数据插入新链表}return NewHead;
}

将反转函数更换后在打印新的链表

三、删除链表的倒数第K个结点

1.遍历链表，求出倒数第K个结点

struct Node* DeleteNode(struct Node* HeadNode, int k) {int count = 0;//count用来计数struct Node* DeleteNode = HeadNode->next;struct Node* DeleteNodeFront = HeadNode;struct Node* p = HeadNode->next;while (HeadNode->next) {count++;HeadNode = HeadNode->next;//遍历链表找到链表一共有多少个结点}int i = 0;for (i = 0; i < count - k; i++) {DeleteNode = DeleteNode->next;DeleteNodeFront = DeleteNodeFront->next;}//当数目不到K的时候，当前结点指向下一结点DeleteNodeFront->next = DeleteNode->next;free(DeleteNode);//删除结点后一定记得freereturn p;
}

输入要删除的倒数第K个结点的K，再次进行打印

2.快慢指针法进行删除

struct Node* DeleteNode(struct Node* HeadNode, int k) {struct Node* p = HeadNode->next;//快指针struct Node* q = HeadNode->next;//慢指针//定义快慢指针分别从表头开始while (p) {if (k < 0) {q = q->next};k--;p = p->next;}//此时快指针比慢指针多走了K步//当p指向NULL时，p比q多走K+1步，直接删除q的下一结点if (k == 0) { return HeadNode->next;}q->next = q->next->next;return HeadNode;
}

代码运行结果如下

四、合并两个有序链表

struct Node* Add(struct Node* l1, struct Node* l2) {if (l1 == NULL) {return l2;//l1为空直接返回l2}if (l2 == NULL) {return l1;//同样l2为空直接返回l1}struct Node* head = (struct ListNode*)malloc(sizeof(struct Node));struct Node* p = head;while (l1 && l2) {//l1,l2都不为空时，比较结点对应数值的大小if (l1->data < l2->data) {p->next = l1;l1 = l1->next;} else {p->next = l2;l2 = l2->next;}p = p->next;}if (l1) {//当l2循环为空时，直接让链表的next指向l1p->next = l1;}if (l2){//当l1循环至空时，指向l2p->next = l2;}return head->next;
}

---

总结

介绍了链表的一些简单的操作，

本文标签： 链表