当前位置: article > 正文

链表基本功能的实现及链表经典OJ题讲解

作者：凡人多烦事01 | 2024-05-30 02:49:03

踩

链表基本功能的实现及链表经典OJ题讲解

一、链表的概念

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

上图的1、2、3、4点我们称作为节点，每个节点都是独立申请下来的空间，他们都拥有着自己的地址。

1.1 节点的构成

节点由两个部分组成，它们分别是数据域和指针域，数据域用来存放数据，而指针域存放着下一个节点的地址，如果下一个节点不存在，则存放的是NULL空指针。

节点的声明:


typedef struct node
{
	int data;
	struct node* next;
};

上面代码的data便是我们说的数据域，结构体指针next便是指针域，指向下一个节点。

1.2 链表的分类

链表一共有八种结构，如下图所示:

链表虽然有八种结构，但实际上我们最常使用的只有两种结构:单链表和双向带头循环链表。

今天我们实现的单链表。

二、实现链表的基本功能(增、删、查、改)

链表的结构体声明:


typedef struct node
{
	int data;
	struct node* next;
}Listnode;
typedef Listnode* LinkList;

2.1 创建链表

想要实现链表的各种功能，首先便是要创建一个链表:


LinkList List_create()
{
	LinkList L, p, s;
	int e;
	L = (LinkList)malloc(sizeof(Listnode));
	L->next = NULL;
	p = L;
	printf("输入数据以-1为结尾结束\n");
	scanf_s("%d", &e);
	while (e != -1)
	{
		s = (LinkList)malloc(sizeof(Listnode));
		s->data = e;
		p->next = s;
		p = s;
		scanf_s("%d", &e);
	}
	p->next = NULL;
	return L;
}

这样我们便可以想创建几个节点就创建几个节点，只要输入的数字不为-1，我们便新创建一个节点，并将新创建的节点尾插到链表中。

2.2 增加数据(插入)

要在链表当中增加数据，其实就是在链表中插入数据。


//插入
LinkList List_insert(LinkList L, int i, int e)
{
	LinkList pre;
	pre = L;
	int temp = 0;
	for (temp = 0; temp < i; temp++)
	{
		pre = pre->next;
	}
	LinkList p;
	p = (LinkList)malloc(sizeof(Listnode));
	p->data = e;
	p->next = pre->next;
	pre->next = p;
	return L;
}

上面的代码就是在第i位节点后进行插入，先用循环找到第i位节点，然后新创建一个节点插入在第i位节点后面。

2.3 删除数据(按值删除)

删除数据其实就是遍历链表，寻找到与你输入的值相同的节点，将这个节点free掉，并将free掉的节点后面的所有节点链接到free掉节点前一个节点上。


//删除
LinkList List_delete(LinkList L, int posdata)
{
	LinkList p, pre;
	pre = NULL;
	p = L;
	while (p->data != posdata)
	{
		pre = p;
		p = p->next;
	}
	pre->next = p->next;
	free(p);
	p = NULL;
	return L;
}

遍历查找到相同值的节点，free掉后将free掉的节点后面的所有节点链接到free掉节点前一个节点上。

2.4 查找数据(按值查找与按位查找)

按值查找:


//按值查找
LinkList find_by_num(LinkList L, int num)
{
	LinkList p = L;
	while (p != NULL && p->data != num)
	{
		p = p->next;
	}
	if (p == NULL)
	{
		printf("未找到!\n");
		exit(0);
	}
	return p;
}

遍历链表，如果遍历过程中找到有节点的值与输入的值相同，则返回与输入值相同的节点，未找到则会打印提示信息并退出程序。

按位查找:


//按位查找
LinkList find_by_wei(LinkList L, int pos)
{
	if (pos < 0)
	{
		printf("查找位置错误!\n");
		exit(-1);
	}
	LinkList p = L;
	int j = 0;
	while (p != NULL && j < pos)
	{
		p = p->next;
		j++;
	}
	return p;
}

以j为计数器，j小于pos时一直向后查找节点，最后便会查找到我们所要查找的那一位节点，最后返回那一位节点。

2.5 修改数据

修改数据便要用到上面所讲的查找数据了，只有我们找到了我们要修改的节点，才能对节点进行修改。


void modify(LinkList L)
{
	int pos = 0;
	int data = 0;
	printf("请输入要修改的位数:\n");
	scanf_s("%d", &pos);
	LinkList change = find_by_wei(L , pos);
	printf("原来的值为:%d\n", change->data);
	printf("请输入您要修改的值:\n");
	scanf_s("%d", &data);
	change->data = data;
}

先输入一个位数，后面按位数进行查找，创建一个change节点来接收返回的找到的节点，对change节点的值进行修改即可实现修改功能。

2.6 所有代码及测试结果

所有代码:


#include<stdio.h>
#include<stdlib.h>
 
typedef struct node
{
	int data;
	struct node* next;
}Listnode;
typedef Listnode* LinkList;
 
 
LinkList List_create()
{
	LinkList L, p, s;
	int e;
	L = (LinkList)malloc(sizeof(Listnode));
	L->next = NULL;
	p = L;
	printf("输入数据以-1为结尾结束\n");
	scanf_s("%d", &e);
	while (e != -1)
	{
		s = (LinkList)malloc(sizeof(Listnode));
		s->data = e;
		p->next = s;
		p = s;
		scanf_s("%d", &e);
	}
	p->next = NULL;
	return L;
}
 
//遍历输出
void print_List(LinkList L)
{
	LinkList p;
	p = L->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
}
 
//插入
LinkList List_insert(LinkList L, int i, int e)
{
	LinkList pre;
	pre = L;
	int temp = 0;
	for (temp = 0; temp < i; temp++)
	{
		pre = pre->next;
	}
	LinkList p;
	p = (LinkList)malloc(sizeof(Listnode));
	p->data = e;
	p->next = pre->next;
	pre->next = p;
	return L;
}
 
//删除
LinkList List_delete(LinkList L, int posdata)
{
	LinkList p, pre;
	pre = NULL;
	p = L;
	while (p->data != posdata)
	{
		pre = p;
		p = p->next;
	}
	pre->next = p->next;
	free(p);
	p = NULL;
	return L;
}
 
//按值查找
LinkList find_by_num(LinkList L, int num)
{
	LinkList p = L;
	while (p != NULL && p->data != num)
	{
		p = p->next;
	}
	if (p == NULL)
	{
		printf("未找到!\n");
		exit(0);
	}
	return p;
}
 
//按位查找
LinkList find_by_wei(LinkList L, int pos)
{
	if (pos < 0)
	{
		printf("查找位置错误!\n");
		exit(-1);
	}
	LinkList p = L;
	int j = 0;
	while (p != NULL && j < pos)
	{
		p = p->next;
		j++;
	}
	return p;
}
 
void modify(LinkList L)
{
	int pos = 0;
	int data = 0;
	printf("请输入要修改的位数:\n");
	scanf_s("%d", &pos);
	LinkList change = find_by_wei(L , pos);
	printf("原来的值为:%d\n", change->data);
	printf("请输入您要修改的值:\n");
	scanf_s("%d", &data);
	change->data = data;
}
 
int main()
{
	LinkList L_a;
	int n, data1, data2, data3, pos;
	L_a = List_create();
	printf("链表a为:\n");
	print_List(L_a);
	printf("\n");
	printf("请输入你要插入的位置和数据:\n");
	scanf_s("%d %d", &n, &data1);
	List_insert(L_a, n, data1);
	printf("插入后的链表a为:\n");
	print_List(L_a);
	printf("\n");
	printf("请输入你要删除的数据:\n");
	scanf_s("%d", &data2);
	List_delete(L_a, data2);
	printf("删除后的链表a为:\n");
	print_List(L_a);
	printf("\n");
	printf("请输入你要查找的值\n");
	scanf_s("%d", &data3);
	LinkList ret = find_by_num(L_a, data3);
	printf("你查找的值的地址为:%p", ret);
	printf("\n");
	printf("请输入你要查找的位数:\n");
	scanf_s("%d", &pos);
	LinkList ret1 = find_by_wei(L_a, pos);
	printf("表a的第%d位的值为:%d", pos, ret1->data);
	printf("\n");
	modify(L_a);
	printf("修改后的表a为:\n");
	print_List(L_a);
	printf("\n");
	return 0;
}

测试结果:

三、链表经典OJ题讲解

经过上面的讲解，大家应该对于链表有了初步的了解，下面我们就来做几个经典的链表OJ题来试试水准。

3.1 力扣141.环型链表

该题目链接:

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/linked-list-cycle/description/

题目要求是，如果链表有环，则返回true，没环则返回false。

这题我们可以使用快慢指针来解决，快指针一次走两步，慢指针一次走一步。如果有环，那么快指针会先进环，慢指针后进环，最后快指针将慢指针追上，即两个指针相遇，即有环，如果无环，那么快慢指针永远不会相遇，即无环。

这个时候也许会有人有疑问，为什么快慢两个指针一定会相遇呢？

假设当slow指针进环时，与fast指针的距离差为N ，如果N是偶数的话，那么第一次便能追上。

那么N是奇数时呢?

我们假设进环前的长度为L，圆环长度为C，距离差为N当N是奇数时，他们第一轮不会相遇，第二轮的距离差就会变为C-1，这时就要判断C-1了，当C-1为偶数时，第二轮就能追上，但当C-1为奇数时，便永远不能相遇了，由此我们可以得出，当N为奇数且C为偶数时，便永远不能相遇，因为当N是奇数时，C-N也为奇数，便永远不能相遇，但可能会出现这种情况吗?

结果是不可能出现这种情况。

我们可以列一个数学公式来看一下：

假设fast的速度为slow的3倍，所以fast走的路程为slow的3倍。

3*L=L+x*C+C-N，其中x为fast所走圆环的圈数。

该公式化简后得:2L=(x+1)C-N，当N为奇数且C为偶数时，(x+1)C为偶数，N为奇数，2L为偶数，偶数－奇数不可能为偶数，所以N为奇数且C为偶数这种情况是一定不存在的，所以快慢指针在有环的情况下一定能在环内相交。

思路有了，下面我们来看下代码:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}

先创建快慢指针指向头结点，

这里我们要注意的是，如果一个链表为空或者只有一个节点，那么这个链表肯定是无环链表。所以我们while的判断条件是fast和fast->next不为空，为空就返回false，不然就进入循环看快慢指针是否会相遇，相遇即证明有环，返回true。

结果:

3.2 力扣142.环型链表||

该题目链接:

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode-cn.com/problems/linked-list-cycle-ii/description/

题目的要求是如果链表无环，则返回NULL，有环则返回环的第一个节点。

这题就是上题的进阶版，我们一样可以使用快慢指针来解决这个问题。

下面我们来解析一下思路:

如上图所说，我们只需找到快慢指针在环中相遇的节点meet，再找到meet与head相遇的节点，meet与head相遇的节点便是环的第一个节点。

下面我们来看代码:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
 
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* fast=head;
    ListNode* slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            ListNode* meet=fast;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

与第一题的代码大致相似，先创建快慢指针通过循环找到快慢指针在环内的相交节点，再让相交节点与头结点同时移动，他们两个相交的节点便是环的第一个节点。

结果：

3.3 力扣138.随机链表的复制

该题目链接:

138. 随机链表的复制 - 力扣（LeetCode）https://leetcode.cn/problems/copy-list-with-random-pointer/description/

该题目的要求是给出一个链表，叫你复制一个链表，并且返回复制链表的头结点。

这是力扣上给出的一个实例，我们都知道节点的next指向的是下一个节点，但我们不知道random指向的是谁，random可能指向节点，也可能指向NULL，这便是本题最难解决的问题。

本题最大的难点就在于如何建立复制链表与原链表的联系，如何找到复制链表random所指向的节点？

这时我们可能就会想到，将对应复制链表的节点插入到对应原链表的节点后，使其构成一个新链表，这样子原链表与复制链表就有了联系。

如上图所示进行插入后，我们既可以找到原链表的节点，也可以找到复制链表的节点，当然上图原链表的random指针指向的节点并没有改变，只是我为了简洁删掉了，这时通过图我们就能发现，复制链表的节点的random指针所指向的节点便是pur的random所指向节点的next，这样我们就解决了最大的问题，将复制链表random所指向的节点解决，接下来只需要将复制链表的节点取下来，一一尾插到一个新链表中，便可以了。

下面我们来看代码:


    Node* pur=head;
    while(pur)
    {
        Node* next=pur->next;
        Node* newnode=(Node*)malloc(sizeof(Node));
        newnode->val=pur->val;
        newnode->next=pur->next;
        pur->next=newnode;
        pur=next;
    }

这是为每个原链表节点创建复制节点并插入在当前原链表节点的后面，所形成的链表为:


    pur=head;
    while(pur)
    {
        Node* copynode=pur->next;
        Node* copynodenext=copynode->next;
        if(pur->random==NULL)
        {
            copynode->random=NULL;
        }
        else
        {
            copynode->random=pur->random->next;
        }
        pur=copynodenext;
    }

这时我们重新给pur赋值为head，重新遍历链表，寻找复制链表节点的random的指向并赋值，这时的链表大概为:

上图为只画了一个节点的链表。

完成这一步后，我们便可以进行最后一步，将复制链表的节点链接成为链表。


    pur=head;
    Node* copynodehead=NULL;
    Node* copynodetail=NULL;
    while(pur)
    {
        Node* copynode=pur->next;
        Node* copynodenext=copynode->next;
        if(copynodehead==NULL)
        {
            copynodehead=copynodetail=copynode;
        }
        else
        {
            copynodetail->next=copynode;
            copynodetail=copynode;
        }
        pur=copynodenext;
    }

这里其实就是进行尾插了，只需要对copyhead是否为空进行一下判断就好，就是一个简单的尾插，尾插后就会形成我们的复制链表，并且复制链表与原链表应该一模一样。

最后我们返回复制链表的头指针就好了。

完整代码:


/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
	Node* pur=head;
    while(pur)
    {
        Node* next=pur->next;
        Node* newnode=(Node*)malloc(sizeof(Node));
        newnode->val=pur->val;
        newnode->next=pur->next;
        pur->next=newnode;
        pur=next;
    }
    pur=head;
    while(pur)
    {
        Node* copynode=pur->next;
        Node* copynodenext=copynode->next;
        if(pur->random==NULL)
        {
            copynode->random=NULL;
        }
        else
        {
            copynode->random=pur->random->next;
        }
        pur=copynodenext;
    }
    pur=head;
    Node* copynodehead=NULL;
    Node* copynodetail=NULL;
    while(pur)
    {
        Node* copynode=pur->next;
        Node* copynodenext=copynode->next;
        if(copynodehead==NULL)
        {
            copynodehead=copynodetail=copynode;
        }
        else
        {
            copynodetail->next=copynode;
            copynodetail=copynode;
        }
        pur=copynodenext;
    }
    return copynodehead;
}

结果:

四、总结

一开始我们讲了链表，并且实现了链表的基本功能(增、删、查、改)，当我们学会了链表的基本功能和操作后，我们便讲了三道链表的经典OJ题，前面两道环型链表难得不是编程而是思路，如果有了思路，那么解决就是时间问题，前两题对于链表的应用还算比较基础，最后一题对于链表的应用较为全面，如果在懂思路的情况下能够独立编写出代码，那么恭喜你，对于链表的理解和应用已经到了大成的境界。

其实我们做完题目后会发现，我们所做的题目基本上都是有关于链表的基本功能，像最常用的便是插入功能，如果我们想要解决这些题目，那么就要对链表的基本功能有所了解，如果连这些都不会的话，那么是解决不了题目的。

说了这么多，希望这些东西能够加深你对于链表的了解，对你能有所帮助。

可能写的不是很好，有问题恳请大家指出，觉得写得好的可以三连哦！谢谢！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/644982