devbox
我家自动化
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2024年最新单链表C语言实现附加力扣题_c语言单链单题 力扣(1)，面试杀手锏

作者：我家自动化 | 2024-05-25 05:10:11

赞

踩

2024年最新单链表C语言实现附加力扣题_c语言单链单题 力扣(1)，面试杀手锏

img
img

网上学习资料一大堆，但如果学到的知识不成体系，遇到问题时只是浅尝辄止，不再深入研究，那么很难做到真正的技术提升。

需要这份系统化的资料的朋友，可以添加戳这里获取

一个人可以走的很快，但一群人才能走的更远！不论你是正从事IT行业的老鸟或是对IT行业感兴趣的新人，都欢迎加入我们的的圈子（技术交流、学习资源、职场吐槽、大厂内推、面试辅导），让我们一起学习成长！

//链表销毁
void SLTNodeDestor(SLTNode \*ps) 
{
	assert(ps);
	while (ps) 
	{
		SLTNode \*del = ps;
		ps = ps->next;
		free(ps);
	}
}


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

打印

请添加图片描述

遍历链表的每个结点，打印这个结点的data

//打印
void SLTprint(SLTNode \*ps) 
{	
	SLTNode \*cur = ps;
	while (cur != NULL) 
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}


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

创建结点

//创建结点
SLTNode \*BuySLTNode(int x) 
{
	SLTNode \*tmp = (SLTNode \*)malloc(sizeof(SLTNode));
	if (!tmp) 
	{
		perror("BuySLTNode::malloc");
		exit(1);
	}
	tmp->data = x;
	tmp->next = NULL;

	return tmp;
}


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

尾插

请添加图片描述

创建一个新的结点newNode，找到最后一个结点的位置tail，用tail链接newNode，这里要注意的是我们的链表的实现是以不带头为目的的，所以会是一个空表，如果是空表的情况下，需要将ps初始化成为第一个结点，往后尾插就只需要找尾了，这里要传二级指针，为了改变外部的指针

//尾插
void SLTPushBack(SLTNode \*\*ps,int x) 
{
	SLTNode \*newNode = BuySLTNode(x);
	//如果是空表
	if (\*ps == NULL) 
	{
		\*ps = newNode;
	}
	else 
	{
		//尾插找尾
		SLTNode \*tail = \*ps;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newNode;
	}
}


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

传递一级指针无法改变main函数的plist的指针，因为是在不同的栈帧中开辟的，只是一份值拷贝，互不影响，所以传递二级指针
在这里插入图片描述

头插

请添加图片描述

头插只需要创建一个新的结点newNode，让新的结点链接ps，再让ps去做新的头，由于需要改变外面的指针，还是要传递二级指针，头插即使是面对链表为空还是不会受影响

//头插
void SLTPushFront(SLTNode \*\*ps,int x) 
{
	SLTNode \*newNode = BuySLTNode(x);
	newNode->next = ps;
	//ps去做新的头
	\*ps = newNode;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

头删

请添加图片描述

头删同样需要改变外面的指针，所以要传二级，移除第一个结点，让第二个结点做新的头

//头删
void SLTPopFront(SLTNode \*\*ps) 
{
	if (\*ps == NULL)
		return;
	SLTNode \*delNode = \*ps;
	\*ps = delNode->next;
	free(delNode);
	delNode = NULL;
}


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

尾删

请添加图片描述

尾删需要考虑三种情况
1、表为空，不需要删除，直接返回
2、只剩一个结点，删除这个结点，再置空，也需要改变外面指针的指向，必须传二级指针
3、有多个结点，定义前驱指针prev，和目标指针cur，当cur指向最后一个结点的时候释放cur，cur置空，前驱指针prev指向空

//尾删
void SLTPopBack(SLTNode \*\*ps) 
{

	SLTNode \*phead = \*ps;
	//只有一个结点
	if (phead->next == NULL)
	{
		free(phead);
		\*ps = NULL;
		phead = NULL;
	}
	//表为空直接返回
	else if (\*ps == NULL) 
	{
		return ;
	}
	//剩多个结点
	else 
	{	
		//定义前驱指针和目标指针
		SLTNode \*tail= \*ps;
		SLTNode \*prev = NULL;
		
		while (tail->next != NULL)
		{
			prev = tail;
			tail= tail->next;
		}
		//移除最后一个结点，让前一个指针指向空
		free(tail);
		cur = NULL;
		prev->next = NULL;
	}
	
}


  • 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

查找

查找54
请添加图片描述

找到该结点就返回，没找到就返回空，空表直接返回

//查找
SLTNode\* SLTFind(SLTNode \*ps, int x) 
{
	if (ps == NULL)
		return NULL;
	SLTNode \*cur = ps;
	while (cur != NULL) 
	{
		if (cur->data == x) 
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}


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

指定位置后插入

在pos后面插入一个新的结点，需要备份pos的下一个结点，先让newNode指向第二个结点再让pos指向newNode

//指定位置后插入
void SLTInsertAfter(SLTNode \*pos, int x) 
{
	assert(pos);
	SLTNode \*next = pos->next;
	SLTNode \*newNode = BuySLTNode(x);
	pos->next = newNode;
	newNode->next = next;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

指定位置前插入

在这里插入图片描述

1、在指定pos的前面插入，如果pos和ps在同一个位置就是头插了
2、如果pos出现在链表的中间某个位置，要想在pos前插入一个新的结点就必须要找到pos前的一个结点prev，让这个结点prev指向新的结点newNode，最后让newNode指向当前结点

//指定位置前插入
void SLTInsertBefor(SLTNode \*\*ps, SLTNode \*pos, int x)
{
	assert(pos);
	SLTNode \*newNode = BuySLTNode(x);
	if (pos == \*ps) 
	{
		newNode->next = \*ps;
		\*ps = newNode;
	}
	else 
	{
		SLTNode \*cur = \*ps;
		SLTNode \*prev = NULL;

		while (cur != pos) 
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = newNode;
		newNode->next = cur;
	}
}


  • 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

指定位置后删除

在这里插入图片描述

next用来保存pos位置的下一个结点，pos指向next的下一个结点，释放next位置的结点

//移除指定位置之后
void SLTEraseAfter(SLTNode \*pos) 
{
	//表为空不做处理
	if(pos == NULL)
	{
		return ;
	}
	assert(pos);
	SLTNode \*next = pos->next;
	pos->next = next->next;
	free(next);
	next = NULL;
}


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

移除指定位置

prev和cur一起一后，当cur与pos相遇了，就将prev链接cur的下一个结点，释放pos位置的结点，将指针置空

在这里插入图片描述

如果plist和pos指向一起，就是头删操作了

在这里插入图片描述

//移除指定位置
void SLTEraseBefor(SLTNode \*\* ps, SLTNode \*pos)
{
	assert(pos);
	SLTNode \*next = pos->next;
	//pos等于ps，头删
	if (\*ps == pos) 
	{
		free(\*ps);
		\*ps = NULL;
		\*ps = next;
	}
	else
	{
		SLTNode \*prev = NULL;
		SLTNode \*cur = \*ps;
		while (cur != pos) 
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = cur->next;
		free(cur);
		cur = NULL;
	}
}


  • 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

力扣题

移除链表元素:

点我.
在这里插入图片描述
考虑两种场景

  • 1、如果表的第一个结点的值就是val，那么就是头删了，释放第一个结点，需要将head的指向改变，指向下一个结点
  • 2、如果表的所有结点全是val的情况，head的指向就可以一直改变，直到指向NULL，最后返回去的就是NULL

链表移除结点的变形题，把特殊场景处理就能搞定

struct ListNode\* removeElements(struct ListNode\* head, int val){
  
    struct ListNode \*prev = NULL;
    struct ListNode \*cur = head;
    while(cur != NULL)
    {
    	//值为val
        struct ListNode \*del = NULL;
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        //值不为val
        else
        {
            //如果cur是头的情况
            struct ListNode \*next = cur->next;
            if(prev == NULL)
            {
                free(cur);
                head = next;
                cur = next;
            }
            //cur不是头
            else
            {
                prev->next = next;
                free(cur);
                cur = next;
            }
        }
    }
    return 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

第二种写法：带哨兵位的头节点，可以让prev指向哨兵位结点，这样就不需要考虑prev是否会存在空指针的问题了，同样的prev和cur一起一后，找到了值位val的结点，就释放该节点，cur继续指向下一个位置，最后只需要返回哨兵位结点的下一个位置

struct ListNode\* removeElements(struct ListNode\* head, int val){
    struct ListNode\* guard = (struct ListNode\*)malloc(sizeof(struct ListNode));
    guard->next = head;

    struct ListNode \*prev = guard;
    struct ListNode \*cur = head;
    while(cur != NULL)
    {
        if(cur->val != val)
        {
            prev = cur;
            cur = cur->next;
        }
        else
        {
            
            struct ListNode \*next = cur->next;
           
            prev->next = next;
            free(cur);
            cur = next;
        }
    }
    return guard->next;
}


  • 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

在这里插入图片描述

206. 反转链表:

点我.
实现思路

使用三个指针迭代的方法，prev和cur用来逆置结点的指向，next保证cur能找到下一个结点的位置，直到cur指向空了，循环停止，返回prev指针，整个链表也就逆置了

struct ListNode\* reverseList(struct ListNode\* head){
    if(head == NULL)
    {
        return NULL;
    }
    
    struct ListNode\* cur = head;
    struct ListNode\* prev = NULL;
    struct ListNode\* next = cur->next;

    while(cur)
    {
       //逆置
       cur->next = prev;
       //迭代
       prev = cur;
       cur = next;
       if(next != NULL)
       next = next->next;
    }

    return prev;
}


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

思路二：必做，链表头插的变型题，将原链表遍历一遍，取原链表的结点头插到新的表中

struct ListNode\* reverseList(struct ListNode\* head){
    struct ListNode \*newhead = NULL;
  
    struct ListNode \*cur = head;
    while(cur)
    {
        struct ListNode \*next = cur->next;
        //头插
        cur->next = newhead;
        newhead = cur;
        //迭代
        cur = next;
    }
    return newhead;
}


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

876. 链表的中间结点:

点我.
在这里插入图片描述

快慢指针解法，快指针走两步慢指针走一步，当快指针走到链表NULL位置的时候，或者快指针走到最后一个结点的位置，循环终止，返回慢指针

struct ListNode\* middleNode(struct ListNode\* head){
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode\* fast = head;
    struct ListNode\* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
       
        fast = fast->next->next;
       
    }

    return slow;
}


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

链表中倒数第k个结点:

点我.
在这里插入图片描述

快指针先走k步，快指针走完k步后，快指针和慢指针一起走，当快指针走完了，slow就是倒数第k个结点，就返回slow的位置

极端情况：如果fast先走k步，k大于链表的长度，链表可能存在空表，是空表就返回NULL

struct ListNode\* FindKthToTail(struct ListNode\* pListHead, int k ) {
    // write code here
    struct ListNode\* fast = pListHead;
    struct ListNode\* slow = pListHead;
    
    while(k--)
    {
        //k大于链表长度，fast已经走到NULL了，
        if(fast == NULL)
            return NULL;
        fast = fast->next;
    }
    
    while(fast)
    {
       fast = fast->next;
       slow = slow->next;
    }
    return slow;
}


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

21. 合并两个有序链表

链接: 点我.
在这里插入图片描述

思路：合并两个链表只需要将原链表中最小的值尾插到新链表中去

struct ListNode\* mergeTwoLists(struct ListNode\* l1, struct ListNode\* l2){
    if(l1 == NULL)
    return l2;
    if(l2 == NULL)
    return l1;
    if(l1 == NULL && l2 == NULL)
    return NULL;
    
    struct ListNode\* newList = NULL;
    struct ListNode \*tail = newList;
	//取下最小值做新链表的头
    if(l1->val < l2->val)
    {
        newList = tail = l1;
        l1 = l1->next;
    }
    else
    {
        newList = tail = l2;
        l2 = l2->next;
    }
	//取两个链表中最小值尾插到新的链表中去
    while(l1 && l2)
    {
       if(l1->val < l2->val)
       {
           tail->next = l1;
           l1 = l1->next;
       }
       else
       {
           tail->next = l2;
           l2 = l2->next;
       }
       tail = tail->next;
    }

	//如果有一个链表还没遍历完就继续尾插到新链表去
    if(l1)
    {
        tail->next = l1;
    }
    if(l2)
    {
        tail->next = l2;
    }

    return newList;
}


  • 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

带哨兵位的头节点不需要考虑新链表头尾都是是NULL的这种情况

struct ListNode\* mergeTwoLists(struct ListNode\* l1, struct ListNode\* l2){
	//创建哨兵头节点
    struct ListNode\* head = (struct ListNode\*)malloc(sizeof(struct ListNode));
    struct ListNode\* tail = head;
    tail->next = NULL;

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

    //还剩的
    if(l1){
        tail->next = l1;
    }
    if(l2){
        tail->next = l2;
    }
	
	//释放动态开辟的结点，返回新的头
    struct ListNode\* node = head;
    head = head->next;
    free(node);
    return 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

OR36 链表的回文结构

链接: 点我 .
在这里插入图片描述

解题思路：先找出中间结点（快慢指针法），将中间结点起始位置往后整体逆置，返回逆置后的头指针，得到后部分逆置的链表，再跟原链比较

class PalindromeList {
public:
    struct ListNode\* middleNode(struct ListNode\* head){
    if(head == NULL)
    {
        return NULL;
    }
    struct ListNode\* fast = head;
    struct ListNode\* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
       
        fast = fast->next->next;
       
    }

    return slow;
}
    struct ListNode\* reverseList(struct ListNode\* head){
    if(head == NULL)
    {
        return NULL;
    }
    
    struct ListNode\* cur = head;
    struct ListNode\* prev = NULL;
    struct ListNode\* next = cur->next;

    while(cur)
    {
       //逆置
       cur->next = prev;
       //迭代
       prev = cur;
       cur = next;
       if(next != NULL)
       next = next->next;
    }

    return prev;
}
    bool chkPalindrome(ListNode\* A) {
        // write code here
        //找到中间结点整体逆置，最后比较
        struct ListNode\* mid = middleNode(A);
        struct ListNode\* rhead = reverseList(mid);
        
        //比较
        while(A && rhead)
        {
            if(A->val != rhead->val)
            {
                return false;
            }
            else
            {
                A = A->next;
                rhead = rhead->next;
            }
        }
        return true;
    }
};


  • 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

在这里插入图片描述
160. 相交链表
链接: 点我.

链表的相交并不是直线的相交，而是两个链表中存在一个公共结点，这样的链表我们可以称它是相交链表，比较结点的地址，如果相同那么就是相交的，否则不是，让长距离的先走差距步，最后再同时走，如果中间相交就返回该结点，否则返回NULL

struct ListNode \*getIntersectionNode(struct ListNode \*headA, struct ListNode \*headB) {
    //记录链表的长度
    int lenA = 0,lenB = 0;
    struct ListNode \*curA = headA;


![img](https://img-blog.csdnimg.cn/img_convert/c8d15002a50694c702d8c16375808cd6.png)
![img](https://img-blog.csdnimg.cn/img_convert/67563b8fc86217494accf3edb57fe52d.png)

**既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上C C++开发知识点，真正体系化！**

**由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新**

**[如果你需要这些资料，可以戳这里获取](https://bbs.csdn.net/topics/618668825)**



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

在这里插入图片描述
160. 相交链表
链接: 点我.

链表的相交并不是直线的相交，而是两个链表中存在一个公共结点，这样的链表我们可以称它是相交链表，比较结点的地址，如果相同那么就是相交的，否则不是，让长距离的先走差距步，最后再同时走，如果中间相交就返回该结点，否则返回NULL

struct ListNode \*getIntersectionNode(struct ListNode \*headA, struct ListNode \*headB) {
    //记录链表的长度
    int lenA = 0,lenB = 0;
    struct ListNode \*curA = headA;


[外链图片转存中...(img-9LxILmYW-1715669456468)]
[外链图片转存中...(img-8w02yCSX-1715669456469)]

**既有适合小白学习的零基础资料，也有适合3年以上经验的小伙伴深入学习提升的进阶课程，涵盖了95%以上C C++开发知识点，真正体系化！**

**由于文件比较多，这里只是将部分目录截图出来，全套包含大厂面经、学习笔记、源码讲义、实战项目、大纲路线、讲解视频，并且后续会持续更新**

**[如果你需要这些资料，可以戳这里获取](https://bbs.csdn.net/topics/618668825)**


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/620673
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号