首页 > 其他分享 >速通数据结构第三站 单链表

速通数据结构第三站 单链表

时间：2024-03-25 17:02:12浏览次数：37  
标签：单链 ListNode cur struct next 链表 tail 第三站 速通

系列文章目录

速通数据结构与算法系列

1   速通数据结构与算法第一站 复杂度          http://t.csdnimg.cn/sxEGF

2   速通数据结构与算法第二站 顺序表 

3   速通数据结构与算法第二站 单链表 

感谢佬们支持！

目录

系列文章目录

  • 前言
  • 一、单链表
  •        1 结构体
  •        2 接口声明
  •        3 打印
  •        4 扩容
  •        5 尾插
  •        6 尾删
  •        7 头插
  •        8 头删
  •        9 find
  •       10 insert(在指定位置后一个插)
  •       11 erase(删指定位置的下一个)
  •       12 销毁
  • 二、OJ题
  •        1 删除链表元素
  •        2 反转链表
  •        3 合并两个有序链表 
  •        4 链表分割
  •        5 链表的中间节点
  •        6 链表的回文结构
  •        7 相交链表
  • 总结

前言

    上一节我们学习了顺序表这一数据结构，这一节我们来学习链表，准确来说是单链表。

链表的用途十分广泛，操作系统的大部分队列都是由双链表维护的；但是单链表依旧有他的优势，

由于比双链表少了一个成员，一个节点的大小会大大减小，所以有的结构为了省内存会使用单链表

，比如哈希表会挂单链表。而且大部分的链表算法题都是以单链表为背景的，面试中问的尤为频繁

一、单链表

单链表的结构体由数据域和指针域组成

数据域用来存数据，指针域用来存下一个节点的地址

我们建3个文件，slist.h,slist.c,test.c

typedef int SLDataType;

typedef struct SListNode
{
	int data;
	struct SListNode* next;
}SLTNode;

由于链表没什么好初始化的，所以我们在声明的接口里不用写初始化函数

还是来看一下声明的接口

接口声明

//打印
void SListPrint(SLTNode* phead);

//销毁
void SListDestroy(SLTNode** pphead);

//增加节点
SLTNode* SListBuyListNode(SLDataType x);

//尾插	
void SListPushBack(SLTNode** pphead, SLDataType x);

//尾删
void SListPopBack(SLTNode** pphead);

//头插
void SListPushFront(SLTNode** pphead, SLDataType x);

//头删
void SListPopFront(SLTNode** pphead);

//寻找
SLTNode* SListFind(SLTNode* phead, SLDataType x);

//指定位置后插
void SListInsertAfter(SLTNode** pphead, SLDataType x, SLTNode* pos);

//删指定位置的下一个
void SListEraseAfter(SLTNode** pphead, SLTNode* pos);

这个时候大家会注意到我们用的全部都是二级指针，为什么呢？

首先，我们定义的就是一个指针，所以传参传的也是指针，如果我们只传原生的指针过去

形参的修改不影响实参，我们在test.c定义的指针还是空

所以我们要传指针的地址过去，也就是二级指针

先来写一波打印

显然，打印并不会修改链表，所以我们只传一级指针就行

由于空的链表也能打印，所以我们不需要assert

void SListPrint(SLTNode* phead)
{
	//由于空的链表也能打印，所以我们不用断言
	//assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
}

扩容

扩容的逻辑也相对简单，直接malloc即可

//增加节点
SLTNode* SListBuyListNode(SLDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//增加失败
	if (NULL == newnode)
	{
		printf("malloc fail\n ");
		exit(-1);
	}
	//增加成功
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

我们先来写一个尾插

尾插

尾插的核心逻辑是先找尾，然后在让 尾->next=newnode;

当然，我们要考虑链表为空的情况由于链表为空是在预期之内的，所以我们不用断言

*pphead,但是要断言pphead

当链表为空时，newnode就是新的头

代码如下

//尾插	
void SListPushBack(SLTNode** pphead, SLDataType x)
{
	assert(pphead);
	SLTNode* newnode = SListBuyListNode(x);
	//链表为空
	if (NULL == *pphead)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		//找到尾
		tail->next = newnode;
	}
}

我们可以简单的做一波测试

SLTNode* plist = NULL;
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 4);
	SListPrint(plist);

（确实挺不错的）

尾删

显然，我们不能删空链表，所以需要断言*pphead

尾删要分两种情况：只有一个节点和不只有一个节点

当只有一个节点时，我们就不用找尾了，直接删

而不止一个节点时要先找尾

代码如下

void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	//尾删不能为空
	assert(*pphead);
	//只有一个节点
	if (((*pphead)->next) == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	SLTNode* tail = *pphead;
	while (tail->next->next)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;
}

我们再做一波测试

SLTNode* plist = NULL;
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 6);
	SListPopBack(&plist);
	SListPrint(plist);
	printf("\n");
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 4);
	SListPopBack(&plist);

	SListPrint(plist);

由此可见，尾插尾删由于要找尾，时间复杂度都是O（n）

这个时候有人要问了：尾插尾删并不改变头指针啊，也就是说只传一级指针也没问题

但如果刚开始链表为空调用尾插和只有一个节点时尾删显然就需要修改了，所以我们依然需要传二级指针

头插

头插就简单多了，给大家画一张图就够了

-》

代码很简单

//头插
void SListPushFront(SLTNode** pphead, SLDataType x)
{
	assert(pphead);
	SLTNode* newnode = SListBuyListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;

}

头删

头删的逻辑一样简单，我们只需提前保存当前头的下一个，再删头即可

//头删
void SListPopFront(SLTNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//提前保存头节点的下一个
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;

	*pphead = next;

}

我们简单的测试一下

SLTNode* plist = NULL;
	SListPushFront(&plist, 6);
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPopFront(&plist);
	SListPrint(plist);

由原理可知：链表的头插和头删都是高贵的O（1），这也就是为什么STL的slist选择提供

push_front()和pop_front()而非push_back()和pop_back()的原因

寻找

寻找返回的是某值所在节点的指针

由于同样不修改链表，所以我们传一级指针

代码如下

/寻找
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{
	SLTNode* cur = phead;
	while (cur->next)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	//没找见
	return NULL;
}

我们再来实现一下insert

我们实现的时特定位置后插，大体逻辑是这样的

//指定位置后插
void SListInsertAfter(SLTNode** pphead, SLDataType x, SLTNode* pos)
{
	assert(pphead);
	//断言pos
	assert(pos);

	SLTNode* newnode = SListBuyListNode(x);
	//处理链接关系
	newnode->next = pos->next;
	pos->next = newnode;
}

再来搞一下erase

erase的逻辑大同小异，我们只需提前保存下一个，改一下链接即可

但是要注意的是由于要删pos的下一个位置，删的这个位置不能为空

//删指定位置的下一个
void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	//断言pos
	assert(pos);
	//删的时候下一个位置不能是空
	assert(pos->next);

	SLTNode* next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;

}

我们再测试一波

SLTNode* plist = NULL;
	SListPushFront(&plist, 6);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 4);


	SLTNode* pos = SListFind(plist, 2);
	SListInsertAfter(&plist, 7, pos);
	SListPrint(plist);
	printf("\n");

	SListEraseAfter(&plist, pos);
	SListPrint(plist);
	SListDestroy(&plist);

最后我们要来写一下销毁

销毁

销毁的逻辑在于你每次都有保存要销毁节点的下一个，然后再销毁当前节点，最后再给头指针置空

//销毁
void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		//提前存好下一个
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	//销毁头指针
	*pphead = NULL;
}

二、OJ题

   我们来挑一些比较经典、面试中会常常问到的相对简单的题目来做。

1 删除链表元素

题目链接： . - 力扣（LeetCode）

这道题有两种方法，我们可以就在链表内部删，也可以取不等于val的尾插至新链表

法一：

删除的逻辑非常简单，就是我们实现单链表的中间删逻辑，定义一前一后两个指针

只需考虑一下头删的情况即可

struct ListNode* removeElements(struct ListNode* head, int val)
{
    if (head == NULL)
    {
        return NULL;
    }

    struct ListNode* Node = head;
    struct ListNode* prev;


    while (Node)
    {
        if (Node->val == val)
        {

            if (Node == head)//ͷɾ
            {
                head = head->next;
            }

            else
            {
                prev->next = Node->next;
                free(Node);
                Node = prev->next;
            }
        }

        else
        {
            prev = Node;
            Node = Node->next;
        }
    }

    return head;
}

法二：

尾插的逻辑也简单，这个时候有个技巧，为了避免每次尾插时都要找尾，我们直接定义一个尾指针每次记录一下即可

简单是简单，但是如果仅考虑到这样写完代码后提交就直接报错了

struct ListNode* removeElements(struct ListNode* head, int X)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead = NULL, * tail = NULL;
    struct ListNode* cur = head;

    while (cur)
    {
        if (cur->val != X)
        {
            if (tail == NULL)
            {
                newhead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = cur;
                // tail->next=NULL;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    return newhead;
}

如果原链表最后一个元素是要删的那个而前一个不是，当我们删了后一个之后，后一个的next就变成了野指针

如图所示

所以我们需要置空尾指针，也就是在最后

tail=tail->next;

此时你再提交，发现依然编不过，此时你会发现这个用例叫【7，7，7，7】 val=7；

由于每个元素都要被删，所以尾指针根本就是空的，不能解引用

所以我们要这样

if (tail)
        tail->next = NULL;

最后的代码是这样的

struct ListNode* removeElements(struct ListNode* head, int X)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead = NULL, * tail = NULL;
    struct ListNode* cur = head;

    while (cur)
    {
        if (cur->val != X)
        {
            if (tail == NULL)
            {
                newhead = tail = cur;
            }
            else
            {
                tail->next = cur;
                tail = cur;
                // tail->next=NULL;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
    }
    if (tail)
        tail->next = NULL;

    return newhead;
}

（最后终于过了）

2 反转链表

题目链接：. - 力扣（LeetCode）

这个题我们可以有两个思路：1遍历链表，改指针指向

显然，双指针是不够的，如图

如果我们改了1到2的指向，那3这个节点就找不到了，所以我们需要三指针

以prev和cur改指向，以next记录下一个节点的位置

最后改完指向时，next为空，我们返回的是cur

所以由于最后一步next可能为空，所以我们每次迭代next前，都要判空

代码如下

 ListNode* reverseList(ListNode* head)
    {
        if (head == nullptr)
            return nullptr;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* next = cur->next;

        while (cur)
        {
            cur->next = prev;
            prev = cur;
            cur = next;
            if (next)
                next = next->next;
        }
        return prev;
    }

也可以有第二种思路

2 遍历原链表，依次头插至新链表

代码如下，也是非常简单

struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead = NULL;
    //ͷ嵽newhead
    struct ListNode* cur = head;

    while (cur)
    {
        struct ListNode* next = cur->next;

        cur->next = newhead;
        newhead = cur;

        //
        cur = next;
    }
    return newhead;
}

3 合并两个有序链表 

题目链接：. - 力扣（LeetCode）

相较于合并两个有序数组，合并两个有序链表就简单多了，我们可以直接找小的尾插

每次标记一下尾指针，尾插的题做起来还是很舒服的。

仅仅考虑一下头为空的情况即可

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;

    struct ListNode* head=NULL, * tail = NULL;
    while (cur1 && cur2)
    {
        if (cur1->val <= cur2->val)
        {
            if (head == NULL)
            {
                head = tail = cur1;
            }
            else
            {
                tail->next = cur1;
                tail = tail->next;
            }
            cur1 = cur1->next;
        }
        else
        {
            if (head == NULL)
            {
                head = tail = cur2;
            }
            else
            {
                tail->next = cur2;
                tail = tail->next;
            }
            cur2 = cur2->next;
        }
    }
    //cur1先结束了
    if (cur1 == NULL)
    {
        tail->next = cur2;
    }

    //cur2先结束了
    if (cur2 == NULL)
    {
        tail->next = cur1;
    }
    return head;
}

还可以用带哨兵位的做法

带了哨兵位的好处就是，我们不用考虑头为空的事情了

虽然力扣不会检测内存泄漏，但我们最好还是free一下我们的头节点

记得临时保存一下，要不然就找不到链表的头啦

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if (list1 == NULL)
    {
        return list2;
    }
    if (list2 == NULL)
    {
        return list1;
    }


    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;

    struct ListNode* guard = NULL, * tail = NULL;
    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;

    while (cur1 && cur2)
    {
        if (cur1->val < cur2->val)
        {
            tail->next = cur1;
            tail = tail->next;
            cur1 = cur1->next;
        }
        else
        {

            tail->next = cur2;
            tail = tail->next;
            cur2 = cur2->next;
        }
    }
    //cur1先结束了
    if (cur1 == NULL)
    {
        tail->next = cur2;
    }

    //cur2先结束了
    if (cur2 == NULL)
    {
        tail->next = cur1;
    }

    struct ListNode* head = guard->next;
    free(guard);
    return head;
}

4 链表分割

链表分割_牛客题霸_牛客网

显然，在一个链表上操作较为麻烦，我们可以开两个链表，将小于x的节点插到一个链表中

将大于x的节点插入另一个链表中，再将两个链表穿起来，返回小链表的头即可

注意：将大链表的头接入小链表的尾时，记得给大链表的尾置空。

代码如下~

ListNode* partition(ListNode* pHead, int x)
    {

        struct ListNode* LessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* GreaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));


        //遍历链表
        ListNode* cur = pHead;

        ListNode* tail1 = LessHead;
        ListNode* tail2 = GreaterHead;


        while (cur)
        {
            if (cur->val < x)
            {
                //小于x就尾插至Less链表
                tail1->next = cur;
                tail1 = cur;
            }
            else
            {
                //否则就尾插至Greater链表

                tail2->next = cur;
                tail2 = cur;
            }
            cur = cur->next;
        }

        //链接两个链表
        tail1->next = GreaterHead->next;
        tail2->next = nullptr;

        //保存下要返回的节点
        struct ListNode* tmp = LessHead->next;
        free(LessHead);
        free(GreaterHead);

        return tmp;
    }

5 链表的中间节点

题目链接 ：. - 力扣（LeetCode）

这个题就简单了，我们可以用快慢指针来做，快指针一次走两步，慢指针一次走一步

当链表长度为奇数时，最后fast->next为空,链表只有一个中间节点

当链表长度为偶数时，最后fast为空,我们的slow将会是两个中间节点的第二个

代码如下

struct ListNode* middleNode(struct ListNode* head)
{
    //ָ
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

6 链表的回文结构

题目链接 . - 力扣（LeetCode）

在前面的铺垫之后，回文链表的思路就简单了，我们先找到链表的中间节点，然后从中间断开

逆置后半段，然后让两个指针遍历，如果有不相同的节点，就不是回文链表。我们可以CV一下之前的中间节点和逆置。

代码如下

class Solution {
public:
struct ListNode* reverseList(struct ListNode* head)
{
    if (head == NULL)
    {
        return NULL;
    }
    struct ListNode* newhead = NULL;
    //ͷ嵽newhead
    struct ListNode* cur = head;

    while (cur)
    {
        struct ListNode* next = cur->next;

        cur->next = newhead;
        newhead = cur;

        //
        cur = next;
    }
    return newhead;
}


    ListNode* middleNode(struct ListNode* head)
{
  //快慢指针
   ListNode*fast=head;
   ListNode*slow=head;
  while(fast&&fast->next)
  {
     fast=fast->next->next;
     slow=slow->next;
  }
  return slow;
}

    bool isPalindrome(ListNode* head) 
    {
        ListNode*middle=middleNode(head);
        ListNode*rmiddle=reverseList(middle);

        while(rmiddle!=nullptr)
        {
            if(rmiddle->val!=head->val)
            {
                return false;
            }
            rmiddle=rmiddle->next;
            head=head->next;
        }
        return true;
    }
};

7 相交链表

题目链接 ：. - 力扣（LeetCode）

显然，两个链表如果相交，那他们的最后一个节点一定相同。

我们可以先遍历一遍两个链表，求出各自的长度，顺便判断一下最后一个节点是否相同，不相同也是直接返回NULL

然后让长的链表先走差距步，再让两个指针一起走，直到遇到相同的节点

值得注意的是，这里两个链表的长度最小为1，所以我们在判断时不能用slow->next和fast->next；而应用slow和fast

代码如下

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    int lenA = 1;
    int lenB = 1;

    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;

    while (tailA)
    {
        lenA++;
        tailA = tailA->next;
    }

    while (tailB)
    {
        lenB++;
        tailB = tailB->next;
    }
    //如果相交，尾节点一定相同  //这个条件很有必要
    if (tailA != tailB)
    {
        return NULL;
    }

    //快的先走差距步，再一起走
    struct ListNode* fast = lenA > lenB ? headA : headB;
    struct ListNode* slow = lenA > lenB ? headB : headA;

    int gap = abs(lenA - lenB);

    while (gap--)
    {
        fast = fast->next;
    }



    while (fast != slow)
    {

        fast = fast->next;
        slow = slow->next;
    }

    return fast;

}

总结

 做总结，单链表由于"不能倒着走"的特性使其在运用上多有限制，这也就是为什么OJ题中的背景

都是单链表，所以在C++11中STL更新了单链表slist用的人也不多。

下篇博客我们将学习双链表，将会轻松很多，但是会接触三个不那么轻松的OJ题。

水平有限，还请各位大佬指正。如果觉得对你有帮助的话，还请三连关注一波。希望大家都能拿到心仪的offer哦。

​

每日gitee侠：今天你交gitee了嘛

标签：单链,ListNode,cur,struct,next,链表,tail,第三站,速通
From： https://blog.csdn.net/qq_73329472/article/details/136872824

相关文章

  • 单链表删除相同的元素
    #include<iostream>#include<stdlib.h>usingnamespacestd;#defineerror-1#defineok1typedefintStatus;typedefintElemType;typedefstructLNode{ ElemTypedata; LNode*next;}LNode,*LinkList;StatusCreateList(LinkList&L,int......
  • 线性表的单链表
    目录1>.单链表的定义和表示2>.单链表基本操作1.初始化2.取值3.查找4.插入5.删除1>.单链表的定义和表示1.基本概念特点：用一组任意的存储单元存储线性表的数据元素（存储单元可以连续，也可以不连续）。对数据元素ai，存储本身的信息和一个指示直接后继的存储位置，这两部分信......
  • 复分析速通
    针对计应数week4的速通。概念复变函数在一点处解析：邻域内有导数。孤立奇点：在该点处不解析但在一去心邻域内解析。ClassA:多项式和指数函数进行加乘及复合。在复平面上每个点处解析。ClassB:ClassA的两个函数相除。只在一些孤立奇点\(z_i\)处不解析，在\(z_i\)的......
  • 速通编译器前端
    编译器前端的概念词法分析及词法分析工具语法分析方法上下文无关文法与左递归的文法与左递归的消除方法递归下降的语法分析方法LL(k)语法分析方法#######first集合#######follow集合LR(k)语法分析方法LALR语法分析方法错误恢复方法语法制导的翻译语法制......
  • Python就该这样学，纯小白速通Python！学习大纲整理，建议保存
    一、学习建议1、找到自己感兴趣的方向，并且结合市场需求进行选择Python的应用范围测试运维web人工智能大数据爬虫及数据分析办公自动化2、学习过程中一定要勤加练习，并且尝试去使用学习过的内容实现一些简答的功能遇到技术问题不要慌，解决问题的过程也是加速自己成长的途......
  • 数据结构（C语言版）——单链表的查找
    1.按位查找//按位查找，返回第i个元素（带头结点）LNode*GetElem(LinkListL,inti){ if(i<0) returnfalse; LNode*p;//指针p指向当前扫描到的结点 intj=0;//当前p指向的是第几个结点 p=L;//L指向头结点，头结点是第0个结点（不存数据） while(p!=NULL&&j<i)......
  • 86 单链表的分解
    你说你会改变，但是你只是为了解决当时的冲突而讲的话。给你一个链表头节点head和x，要求链表中所有小于x的节点都出现在大于或等于x的节点之前例如：head=[1,4,3,2,5,2],x=3;输出：[1,2,2,4,3,5]在合并两个链表的时候，是将两个链表合并成一个，拆分的时候，是将一个链表拆分成两个。......
  • 探索数据结构：单链表的实战指南
    ✨✨欢迎大家来到贝蒂大讲堂✨✨......
  • C 语言整数单链表的表示和实现 数据结构课程设计报告
     数据结构课程设计报告专业名称：计算机科学与技术 课程名称：数据结构        实训题目：整数单链表的表示和实现                           实训环境：C语言实现（DevC++）                    ......
  • 数据结构（一）单链表---以题为例
    实现一个单链表，链表初始为空，支持三种操作：向链表头插入一个数；删除第 k 个插入的数后面的数；在第 k 个插入的数后插入一个数。现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99