- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

LeetCode刷题总结 -- 链表篇

看，未来发表于 2020/12/30 00:08:24 2020/12/30

【摘要】因为去学别的东西，也就两个月没刷题，结果该忘记的不该忘记的都忘记了。思来想去，还是做个总结要来的好些。不涉及那些奇思妙想的题目，就纪录最基本的东西。文章目录本篇将重点讲链表的基本操作（增删查改）public.hmy_list.c 概览创建节点新增节点指定位置插入节点删除节点问题代码1:问题代码2得出经验翻转链表关于链表成环的处理办法 ...

因为去学别的东西，也就两个月没刷题，结果该忘记的不该忘记的都忘记了。
思来想去，还是做个总结要来的好些。
不涉及那些奇思妙想的题目，就纪录最基本的东西。

文章目录

本篇将重点讲链表的基本操作（增删查改）

做链表的题目，总会遇到各种各样莫名其妙的问题，刚刚又解决一个卡了一下午的，原因是用于插入的节点是在循环之外分配空间的（为了省空间），之后没做清理，导致问题，而我的聚焦点却一直在：为什么使用了

temp = head; 
···
temp = temp->next;
··· 
return head;

  
 
  1
  2
  3
  4
  5

之后，head居然也跟着偏了？不应该啊。

一切的一切，都源于对基础的把控不够。

所以，本篇我将致力于尽可能的剖析 “增删查改” 这几个基础到尘埃的函数。

如果觉得自己已经深刻领悟了这些操作的小伙伴，可以先去干别的事情了。

public.h

//这是一个通用链表基本操作的头文件

#include <stdio.h>	
#include <conio.h>
#include <stdlib.h>
#include <memory.h>
#include <assert.h>

//节点数据结构体
typedef struct test
{ char name[12];		//名字
	char pwd[8];		//密码
	int number;			//编号
	int flag;			//区分管理员和用户	// 	0 超级管理员 1 管理员  2 普通用户 3 屏蔽用户
	int money;			//仅用户有存款，初始500
	
} TEST_T;

//如果不多来一个数据域，怎么能体现出通用链表的优势
typedef struct reported
{
	int amount;//交易金额
	int rflag; //交易方式	1、存款 2、取款 3、转账转出 4、转账转入
	int lastmoney;//余额
	int lastmoney2;//收款者的余额
	int number1;//付款账户
	int number2;//入款账户
	char time[12];//操作时间
} REPORT_T;


//节点描述结构体
typedef struct point
{
	void *pData; //指向数据域
	struct point *next;			//指向下一个节点
	
} POINT_T;

POINT_T * head ;
extern POINT_T * head;


  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44

my_list.c 概览

//创建结点/
POINT_T * creat(void *data )	//创建一个属于结构体point的函数，
//传入结构体test的指针便可以用以操作test变量，
{ //并返回一个point的指针用以操作point函数
	POINT_T *p=NULL; p=(POINT_T *)malloc(sizeof(POINT_T));
	if(p==NULL)
	{
		gotoxy(36,14); printf("申请内存失败");
		exit(-1);
	}
	memset(p,0,sizeof(POINT_T)); p->pData=data;
	p->next=NULL;
	return p;
}

/新增节点///
void add(POINT_T * the_head,void *data ) //这里的data不会和上面那个冲突吗？
{
	POINT_T * pNode=the_head;
	POINT_T *ls=creat(data);
	//后面再接上一个
	while (pNode->next != NULL) //遍历链表，找到最后一个节点
	{
		pNode=pNode->next;
	}
	pNode->next=ls;			//ls 临时
}

删除节点/
void Del (POINT_T * the_head, int index)
{
	POINT_T *pFree=NULL; POINT_T *pNode=the_head;
	int flag=0;
	while (pNode->next!=NULL)
	{
		if(flag==index-1)
		{ pFree=pNode->next; //再指向数据域就爆了 pNode->next=pNode->next->next; free(pFree->pData); free(pFree); break;
		}
		pNode=pNode->next;
		flag++;	
	}	
}

///计算节点数
int Count(POINT_T * the_head)
{
	int count=0;
	POINT_T *pNode1=the_head;
	while (pNode1->next!=NULL)
	{
		if(pNode1->next!=NULL)
		{ pNode1=pNode1->next; count++;
		} }	
	return count;
}

/查找固定节点数据//
POINT_T * find(POINT_T *the_head,int index)
{
	int f=0;
	POINT_T *pNode=NULL;
	int count=0;
	pNode=the_head; count=Count(the_head); if(count<index) printf("find nothing"); while(pNode->next!=NULL)
	{
		if(index==f) return pNode;
		pNode=pNode->next;
		f++; }
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92

创建节点

//创建结点/
POINT_T * creat(void *data )	//创建一个属于结构体point的函数， //传入结构体test的指针便可以用以操作test变量，
{ //并返回一个point的指针用以操作point函数
	POINT_T *p=NULL;			//每一个新节点都要置为空
	p=(POINT_T *)malloc(sizeof(POINT_T));//为新节点开辟空间
	if(p==NULL)
	{
		printf("申请内存失败");
		exit(-1);
	}
	memset(p,0,sizeof(POINT_T));//再次确保新节点清理干净了 p->pData=data; //再为新节点赋值
	p->next=NULL; //将新节点置为无后
	return p; //返回此节点
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

新增节点

/新增节点///
void add(POINT_T * the_head,void *data ) //这里的data不会和上面那个冲突吗？
{
	POINT_T * pNode=the_head; //pNode和head指向同一块内存地址，但是pNode和head是互相独立的
	POINT_T *ls=creat(data);
	//后面再接上一个
	while (pNode->next != NULL) //遍历链表，找到最后一个节点
	{
		pNode=pNode->next; //pNode和head是互相独立的，所以此举并不会对head指向的位置进行修改
	}
	pNode->next=ls;			//ls 临时
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

指定位置插入节点

/插入节点///
void add(POINT_T * the_head,int index,void *data ) //这里的data不会和上面那个冲突吗？
{
	POINT_T * pNode=the_head; //pNode和head指向同一块内存地址，但是pNode和head是互相独立的
	POINT_T *ls=creat(data);
	//后面再接上一个
	int i = 0;
	while (pNode->next != NULL && i<index)	
	{
		pNode=pNode->next; //pNode和head是互相独立的，所以此举并不会对head指向的位置进行修改
	}
	ls->next = pNode->next;	//先将链表后部分接到新节点后面
	pNode->next=ls;			//再往链表前部分接上新节点
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14

删除节点

删除节点/
void Del (POINT_T * the_head, int index)
{
	POINT_T *pFree=NULL; POINT_T *pNode=the_head;
	int flag=0;
	while (pNode->next!=NULL)
	{
		if(flag==index-1)
		{ pFree=pNode->next; //再指向数据域就爆了 pNode->next=pNode->next->next; free(pFree->pData); //释放数据域 free(pFree); //释放指针域 break;
		}
		pNode=pNode->next;
		flag++;	
	}	
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

将这些函数一个一个分开写就不容易出错，但是合在一起的时候，问题就要出来了：

问题代码1:

struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(NULL) {} };

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { //传进来的参数不为空 ListNode* temp1 = list1; ListNode* temp2 = list2; //ListNode* temp3 = new ListNode(0);	这要是放这里了问题就大了 while (temp1->next != NULL && temp2!= NULL) { if (temp1->next->val >= temp2->val) { ListNode* temp3 = new ListNode(0);  //这个要放在这里，新插入的节点一定要是新鲜的 temp3->val = temp2->val;  //这里要注意，对新指针赋值，一定要只赋值给单指针，不要把后面一串全弄过去，会出现环状链表 temp3->next = temp1->next; temp1->next = temp3; temp2 = temp2->next; } temp1 = temp1->next; } if (temp2!= NULL) { temp1->next = temp2; } return list1;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28

问题代码2

这就是一个典型的成环链表。

//ListNode* reverseList(ListNode* head)
//{
// ListNode* node_temp;
// ListNode* new_head;
//
// node_temp = head;
// //遍历一个节点，就把它拿下来放到头去
// while (head->next != NULL)
// {
// //先考虑只又两个节点的情况 
// head = head->next;
// new_head = head;
// new_head->next = node_temp;
// node_temp = new_head;
// }
// return new_head;
//}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17

得出经验

链表的题目吧，可以把上面那些拆分好的函数直接拿去用，将复杂的逻辑拆解之后就没那么烦了。

没必要非要挤在一块儿写

翻转链表

ListNode* reverseList(ListNode* head) 
{ ListNode* node_temp = NULL; //这里设为NULL ListNode* new_head = NULL;   //链栈的头 //遍历一个节点，就把它拿下来放到头去 while (head != NULL) { node_temp = head;   //先将节点取出 //先考虑只又两个节点的情况  head = head->next;  //这个不放这里又成环了 node_temp->next = new_head;
	//刚开始相当于是置空的，因为前面并没有分配空间，而是NULL，这也是这个算法不成环的保证 new_head= node_temp; } return new_head;
} 
  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18

关于链表成环的处理办法

链表误成环

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/107235196

点赞
收藏
关注作者

0/1000

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

加入云驻计划，成为创作者

华为云周边好礼
免费体验产品
特殊身份标识
线下官方门票
内部专家零距离
与10000+优质创作者共同成长

立即加入