想入门数据结构,却总是拜倒在链表的石榴裙下?
相信很多小猿人在初入数据结构的时候，或者说是在学习c语言的后期时分，总会遇到一个馋（缠）人的绕来绕去的家伙–就是我们今天要讲的链表。为什么说链表缠人呢，链表的分类，题型的多样性，链表的用途等等
大家好,我是melo,一名大二上软件工程在读生,经历了一年的摸滚,现在已经在工作室里边准备开发后台项目啦
不过这篇文章呢,还是想跟大家聊一聊数据结构与算法,学校也是大二上才开设了数据结构这门课,希望可以一边学习数据结构一边积累后台项目开发经验
写在前边
相信很多小猿人在初入数据结构的时候，或者说是在学习c语言的后期时分，总会遇到一个馋（缠）人的绕来绕去的家伙–就是我们今天要讲的链表。为什么说链表缠人呢，链表的分类，题型的多样性，链表的用途等等都是很多的，限于篇幅本篇着重来讨论一下学习链表以及做题时的思路概览,注意点以及有哪些小技巧
另外,本博客题解一般会使用c(学校课内要求)和java(个人后台方向需要熟练应用)两种语言
ps：本博客旨在提供一些学习和做题时的小技巧，推荐搭配数据结构算法书籍一同学习和补充知识点
入门的话比较推荐的有《啊哈！算法》，《大话数据结构》，这两本书都偏向图文式教学，也有很多可可爱爱的插画
小哈确实好可爱啊哈哈哈
- 关于链表的定义，优点相信你们也都在书中看了蛮多了，这里就不多加阐述，我们直接来看形形色色的各种链表，看他们的区别和实现
链表的分类
我们先来看看最简单的单向链表
- 链表是有序的列表，但是它在内存中是这样存储的
1)链表是以节点的方式来存储,是链式存储
2)每个节点包含data域，next域：指向下一个节点.
3)如图：发现链表的各个节点不一定是连续存储.
4)链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定
带头结点逻辑结构示意图如下
head中不存储实际的数据data，只是用next来指向真正带有数据的第一个节点
不带头结点
第一个节点即存储有实际数据data和next的实际节点
何时要头结点何时不需要呢
- 有无头结点的区别在于，链表的第一个节点是否存储值。那我们可以先大概下个定义：如果说我们的操作会影响到第一个节点的(比如说删除链表中的某个值)，那是不是我们尽量就用带头结点的会好一点
例如：删除结点时，如果我们不带头结点的话，如果删除的是第一个实际节点，那我们还需要去更改头结点，让头结点指向第二个实际节点(因为第一个实际节点已经被删除了，自然就不是头结点了)
而带有头结点的话，恰好就能解决这种需要特判的情况
这个区别，还需要我们慢慢去体会，在下文讲到链表删除的时候自然而然就会更加深刻体会到了，这里只是先点一下，而到了后边环形链表的时候，更多的是没带头结点的版本
Typedef(偷懒神器)
- PNODE就等价于 struct Node* 了!
LinkList就直接等价于struct LNode*，可以省去很多书写，下文中也会体现到
创建链表
思路概览
- 我们需要两个结点，一个指向当前节点，一个指向我们新创建的节点，每次创建新节点后，让当前节点指向新节点，并移动当前节点到新节点上
记得最后跳出循环的时候，要让当前节点指向null来结束链表！
流程
链表节点定义(typedef妙用,后续可以省去struct)
#include<cstdio>
#include <malloc.h>
typedef struct ListNode {
int val;
struct ListNode* next;
};
注意c语言需要修改头文件中的cstido为stdio.h
注意让当前pNow=head
可以省去特判i=0
//根据读取的元素创建链表
ListNode* creatLinkedList() {
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
ListNode* pNow = head;
int n,temp;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
ListNode* pNew = (ListNode*)malloc(sizeof(ListNode));
scanf("%d", &(pNew->val));
//若是第一个
/*if (i == 0) {
head->next = pNew;
}*/
//将当前节点指向新节点,并移动当前节点到新节点上
pNow->next = pNew;
pNow = pNew;
}
//跳出循环后,使得当前节点指向null终止链表
pNow->next = NULL;
return head;
}
特判第一个多一步 head->next=pNew
其实可以不用，在不带头结点的链表创建中，才需要去特判头结点
记住最后跳出循环让pNow->next=null
遍历链表
- 注意让p=head->next，然后遍历p（p=p->next）判断 p !=null 即可
//遍历链表
void traverseLinkedList(ListNode* head) {
for (ListNode* p = head->next; p != NULL; p=p->next) {
printf("%d ", p->val);
}
}
链表插入
在指定位置插入
思路概览
- 首先我们第一感觉就是邀先移动到指定位置的前一位p，然后去新开辟一个节点pNew，让p指向pNew，pNew指向原来p的下一节点
问题
- 如果我们原原本本按照思路来，有没有发现，其实让pNew指向原来p的下一节点，但是此时p的下一节点是什么呢，其实已经是pNew了
所以我们应该先用另一个指针，存储一下原来p都下一个节点
或者说注意一下顺序，先让pNew的next=p的next
然后再让p都next=pNew
注意
**校验合法性
- 用while 和if 两个条件刚好相反 可以省去获取链表长度的操作
//链表插入(三种情况都综合成一种)
bool insertLinkedList(ListNode* head, int position, int data) {
int i = 0;
ListNode* p = head;
ListNode* pNew = (ListNode*)malloc(sizeof(ListNode));
//移动p直到目标位置的前一位,条件是p不为null
while (i < position - 1 && p!=NULL) {
i++;
p = p->next;
}
//若移动不到,返回false
if (i != position - 1 || p==NULL) {
return false;
}
pNew->val = data;
//注意顺序
//先让新节点指向上一个节点的下一节点
//然后再让上一个节点指向新节点
pNew->next = p->next;
p->next = pNew;
return true;
}
链表删除
(力扣)203移除链表元素(删除所有满足指定值的节点)
思路概览
- 我们需要定义两个指针，一个last记录前一个节点，一个记录当前节点now，怎么删除呢？让last(图中的p)->next=now(图中的q)->next就可以了
***递归还未看
https://leetcode-cn.com/problems/remove-linked-list-elements/
特判头指针法
struct ListNode* removeElements(struct ListNode* head, int val){
//前指针
struct ListNode* last=head;
//当前指针
struct ListNode* now=head;
//now肯定要移动,而last就不一定要移动了!!!(此处注意)
for(;now!=NULL;now=now->next){
if(now->val==val){
//特判删除头节点
if(now==head){
head=now->next;
}
//一般情况
else{
last->next=now->next;
}
}
//不删,则移动last,若删了就不用移动!!!
else{
last=now;
}
}
return head;
}
注意last需不需要移动!!!,且last默认先给头节点
虚拟头结点法(注意最后return)
struct ListNode_ dummyHead= (struct ListNode_)malloc(sizeof(struct ListNode));
struct ListNode* removeElements(struct ListNode* head, int val){
//创建虚拟头节点,并指向第一个节点
struct ListNode* dummyHead= (struct ListNode*)malloc(sizeof(struct ListNode));
dummyHead->next=head;
//前指针
struct ListNode* last=dummyHead;
//当前指针
struct ListNode* now=head;
//now肯定要移动,而last就不一定要移动了!!!(此处注意)
for(;now!=NULL;now=now->next){
if(now->val==val){
//特判删除头节点
last->next=now->next;
}
//不删,则移动last,若删了就不用移动!!!
else{
last=now;
}
}
return dummyHead->next;
}
(最优)while+虚拟头
delete temp是c++中的，此处java会自动回收无需释放空间
class Solution {
public ListNode removeElements(ListNode head, int val) {
//创建虚拟头结点
ListNode dummyHead = new ListNode(0);
//让虚拟头结点指向给定的head结点
dummyHead.next = head;
//定义一个临时结点来遍历，默认从虚拟头结点开始
ListNode temp = dummyHead;
while (temp.next != null) {
if (temp.next.val == val) {
//找到了则删除
temp.next = temp.next.next;
} else {
//找不到继续移动
temp = temp.next;
}
}
return dummyHead.next;
}
}
**移除链表元素(指定位置)
题目
题解
#include "allinclude.h" //DO NOT edit this line
Status Delete_L(LinkList L, int i, ElemType &e)
{ // Add your code here
LNode* p = L;
int j=0;
//注意跟新增一个节点不一样,此处得p->next!=NULL
while(j<i-1&&p->next!=NULL){
p=p->next;
j++;
}
//若参数不合法
if(j!=i-1||p->next==NULL){
return ERROR;
}
e= (p->next)->data;
//LNode* temp = p->next;
p->next = p->next->next;
//free(temp);
return OK;
}
**注意
- 跟新增一个节点不一样,此处得p->next!=NULL,而不是p!=NULL
若是p!=NULL的话,下边我们又要保存p->next,可能就非法访问了!
*从第i元素起的所有元素从链表移除
题目
还记得上文的typedef吗,此处定义了一个LinkList就等价于LNode*
相当于Typedef struct LNode LinkList*
题解
#include "allinclude.h" //DO NOT edit this line
Status Split_L(LinkList L, LinkList &Li, int i)
{ // Add your code here
int cnt=0;
LNode* p = L ;
LinkList temp;
//移动到前一位
while(cnt<i-1 && p->next!=NULL){
p=p->next;
cnt++;
}
//校验参数合法性
if(cnt!=i-1||p->next==NULL){
Li=NULL;
return ERROR;
}
temp=(LinkList)malloc(sizeof(LNode));
if(temp==NULL) return ERROR;
Li=temp;
Li->next=p->next;
//销毁i元素后
p->next=NULL;
return OK;
}
链表反转
(力扣)206反转链表
思路概览
- 让后一个指向前一个，同时要记得要用另外一个指针保存下一个节点位置用于正常遍历，总共需要三个指针
官方题解(迭代+三指针)
c语言
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
//先记录curr的下一位,后续才能修改curr的下一位(总结就是要修改哪个值,就先保存下来)
struct ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
java版
区别就在于java没有指针而是引用,直接ListNode就好,没有那个*(写法方便一些)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Tips
要改变什么值,就先用一个临时值来存储
链表反转中,要改变next,又怕影响正常的遍历,所以先用一个临时指针来存储就好了,这样就还能正常的遍历下去
合并两个有序链表
(力扣)21合并两个有序链表
思路
- 同时遍历两个链表l1和l2，直到有一个为null
- 每次遍历时，判断是哪个比较小，然后加到新链表中，移动l1指针
直接if单独比较版本
一次只能一个,但是就不用嵌套while(while还要再次判断是不是空)
struct ListNode* mergeTwoLists2(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* drummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* Node = drummyHead;
while (l1 != NULL && l2 != NULL) {
if( l1->val <= l2->val) {
Node->next = l1;
l1 = l1->next;
}
else{
Node->next = l2;
l2 = l2->next;
}
Node = Node->next;
}
//最后出循环必有一个为null(而且不会同时为null)则让非空的剩余部分连上去即可
Node->next = l1 == NULL ? l2 : l1;
/*ListNode* p = drummyHead->next;
while (p) {
printf("%d", p->val);
p = p->next;
}*/
return drummyHead->next;
}
while中嵌套while版本
注意
内部while可能会破坏外部大while的条件,需要再次判断
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* drummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* Node = drummyHead;
while (l1 != NULL && l2 != NULL) {
while (l1 != NULL && l2 != NULL && l1->val <= l2->val) {
Node->next = l1;
Node = Node->next;
l1 = l1->next;
}
//可能l1已经为NULL了,所以也还得判断l1
while (l2 != NULL && l1 != NULL && l2->val <= l1->val) {
Node->next = l2;
Node = Node->next;
l2 = l2->next;
}
}
//最后出循环必有一个为null(而且不会同时为null)则让非空的剩余部分连上去即可
Node->next = l1 == NULL ? l2 : l1;
/*ListNode* p = drummyHead->next;
while (p) {
printf("%d", p->val);
p = p->next;
}*/
return drummyHead->next;
}
总结
Tip
巧用typedef偷懒神器
有时候题目给的是不带头结点的,尽量自己去构造一个虚拟头指针,可以省去一些特判的操作
要改变什么值,就先用一个临时值来存储
链表反转中,要改变next,又怕影响正常的遍历,所以先用一个临时指针来存储就好了,这样就还能正常的遍历下去
最后
- 有关其他链表知识,环形链表,约瑟夫等经典问题,melo最近比较忙,忙于学习多线程知识和接管一下项目,等到以后学校课程(小声bb学校刚讲到创建和遍历链表)跟进了再后续补充,后续也会更新一些多线程的知识以及设计模式等内容,希望大家多多体谅和包涵
最近学校讲到栈和队列了,过段时间应该也会继续更进完善栈和队列相关的博客