【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)

这篇具有很好参考价值的文章主要介绍了【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

还不清楚链表的码喵们可以看看前篇关于链表的详解


1.链表面试题

既然已经懂得了链表该如何实现,那么现在就趁热打铁开始练习!这里给码喵们整理了相对不错的一些OJ题来练习

1. 删除链表中等于给定值 val 的所有结点。

 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

思路:遍历整个表,访问每个表的值并且删除再将next的指针指向下一个节点

此题比较简单,但是有几个要点来考虑:

  1. 如果第一位是需要删除的数

  2. 执行删除时要如何保存此值的地址来进行空间释放

  3. 等于val值执行删除

  4. 不等于val的值执行向下遍历

附原代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode *tail=head;
    struct ListNode *prev=NULL; //用于记录节点在free掉的时候避免找不到
    
    while(tail!=NULL)   //不为尾节点向后遍历
    {
        if(tail->val == val)    //如果第一位是需要删除的数
        {
            if(tail==head)
            {
                head=tail->next;
                free(tail);
                tail = head;
            }
            else                //执行删除节点,并且free掉空间避免空指针或溢出
            {
            prev->next = tail->next;
            free(tail);
            tail = prev->next;
            }
        }
        else
        {
            prev = tail;
            tail=tail->next;
        }
    }
    return head;
 }

2. 反转一个单链表。

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

本题有些难度,但是掌握好方法后类似的题就能做到运筹帷幄(决胜千里之外)

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++
做题的要点是画图

万事开头难,掌握方法微妙,刚开始我做这题的时候想的是把他变成一个循环指针然后再标记头指针并且实现反转,不知道这样的办法大家有没有试过哈哈,现在我们来用更简单的方法吧。

我们来指定三个指针,前两个指针用于将前一个的指针记录并且连接,第三个指针负责向后遍历直到为空

方法1

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

定义三个指针

n1滞空用于将头指针变成新链表的尾指针,所以滞空

n2 ,n3向后遍历

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

首先我们让n2的下一个结点指向n1,实现第二和第一个节点的相连,再让n2=n3改变n2的地址,再让n3向下一个节点移动

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

n3再向下一个节点移动,之后循环到n2为空地址,就完成了所有节点的反转了。

注意要点:文章来源地址https://www.toymoban.com/news/detail-837210.html

  1. 链表初始值为空要怎么处理
  2. 链表的n2最终到哪里才算结束反转
  3. 指针n3的下一个节点若为空怎么办(不能赋值否则会越界)

附原代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode * n1,*n2,*n3;
    n1=NULL;
    n2=head;
    if(n2)
        n3=n2->next;

    while(n2)
    {
        n2->next = n1;

        n1=n2;
        n2 = n3;

        if(n3)
            n3=n3->next;
    }
    return n1;
}

方法2

我们可以采用头插到新表的方法实现反转,头插进NULL的表,每次插入的数据就是原表按顺序遍历。

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

定义一个新表为空

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

再让原表的cur的下一个节点指向newhead,这样就实现了头插,然后我们再定义一个指针来记录原cur的下一个节点,最后再将newhead指向cur,cur指向下一个节点next.

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

循环这个操作,直到cur为NULL

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

返回newhead

附原代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newhead = NULL;

    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next = newhead;    //指向新节点
        newhead = cur;

        cur = next;
    } 
   return newhead;
}

3. 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

这就要运用上非常巧妙的方法了,既然上一题我们用到了三个指针,这道题我们也用指针来做,但是只用两个指针就好

方法

我们定义两个指针都在头节点向后遍历,但是一个节点一次走一步,一个节点一次走两步

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

当tail走到最后的节点时,head节点刚好返回的就是中间值。

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

注意要点:

  1. tail走两步,head走一步,返回head的地址就是中间的地址
  2. 如果tail走到尾要怎么处理

附源代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
     struct ListNode* tail = head;
     while(tail->next)
     {
         head=head->next;
         tail=tail->next;
         if(tail->next==NULL)
         {
         //head=head->next;
         }
         else
         tail=tail->next;
     }
     return head;

    // struct ListNode* tail = head;
    // int count=0;
    // while(tail->next)
    // {
    //     count++;
    //     tail = tail->next;
    // }
    // if(count%2!=0)
    // {
    //     count=(count+1)/2;
    // }
    // else
    // count/=2;
    // while(count--)
    // {
    //     head=head->next;
    // }
    // return head;
}

4. 输入一个链表,输出该链表中倒数第k个结点。 

链表中倒数第k个结点_牛客题霸_牛客网

此题是上一题的升级版,方法相似,上一题是相对移动,本体是相对距离再移动

方法

这次我们定义两个指针,一个first指针先向前走k步,之后在first和tail指针一起向前走,直到first指针走到结尾,返回tail指针

注意要点

  1. first指针走到尾该如何处理
  2. 空的链表该如何处理
  3. k等于链表的长度该返回什么值(返回第一个节点)
  4. k大于链表的长度该返回什么值(不是我想思考,是nt牛客的测试用例真有这几点,吃饱撑着)

附源代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
	if (pListHead == NULL)	//链表为空直接返回NULL
	{
		return pListHead;
	}
	struct ListNode* first = pListHead;
	struct ListNode* tail = pListHead;

	while (first->next)	//直到first走到尾
	{
		while (k > 0 && first->next)	//k没减到0并且first还没走到尾进入循环
		{
			k--;	//这里用k自减1来进行k次循环的实现(k=0侧不执行)
			first = first->next;
			//if (first->next == NULL && k > 0)
			//{
			//	return NULL;
			//}
		}
		if (first->next == NULL&&k==1)		//当k减到1并且first已经走到尾
		{
			return tail;				//我们就可以直接返回tail的值,这就是返回第一个节点
		}
		else if(k>1)					//如果first到达尾,并且k还大于1,那就是k大于整个链表长度的情况
		{
			return NULL;				//直接返回NULL
		}
		tail = tail->next;		//tail向下走一步
		first = first->next;	//frist向下走一步
	}
	//tail=tail->next;
	return tail->next;
}



    // int count = k;

    // while(first->next)
    // {
    //     first=first->next;
    // }
    //     int len = count;
    // while(tail->next)
    // {
    //     while(len--)
    //     {
    //         tail=tail->next;
    //     }
    //     if(tail!=first)
    //     {
    //         len = count;
    //     }
    //     else 
    //     {
    //         return pListHead->next;
    //     }

    //     pListHead = tail;
    // }
    // return 0;
    // write code here

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有 结点组成的。

力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

方法

照图来看,我们可以很明显的知道我们可以把新的数据放入“新的“链表,这里的引号,意思是这种合并的题目,我们可以不创建新的空间,因为链表的特性,就是每个都是一块独立的空间,而我们就可以把这些表重新”排序“使之形成一个新的链表,而这里的排序方法就是:比较较小值,尾插入新表中。

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

新建两个链表

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

当新表为空时,将较小值(list1)的地址直接赋值,并且更新list1使之向后走,这里因为list1、list2相等,所以随便取一个就行。

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

依此类推,list2、list1对比时,list2较小,将list2赋值list3,同时更新。

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

最后当其中一个表(list2)所有值都赋值给新表后,在把另一个表的所有值直接尾插到新表就OK了,不管另一个表后有多少个值,都可以直接尾插并且完成链表的合并

【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析),数据结构,数据结构,链表,c语言,算法,开发语言,c++

之后返回我们记录的tail就完成了(真是功夫不负有心人啊)

注意要点:

  1. 初始创建表时,首节点为空,我们要让它赋值原表的地址,应该分类讨论
  2. 注意各表的更新
  3. 当其中一个表中所有的值都赋值完毕,另外一个表就可以全部尾插入新表中
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    struct ListNode* list3=NULL;
    struct ListNode* tail=NULL;
    if(list1==NULL)
    {
        return list2;   //若其中一个表为空则返回另一个表
    }
    if(list2==NULL)
    {
        return list1;   //若其中一个表为空则返回另一个表
    }

    while(list1&&list2)
    {
        if(list1->val>list2->val)   //返回小的值
        {
            if(list3==NULL)
            {
                tail=list3=list2;   //如果新链表没有头则把较小值的地址赋值
            }
            else
            {
                list3->next = list2;    //新链表的下一个节点指向较小值
                list3=list3->next;      //更新新链表
            }
            list2=list2->next;          //更新已被赋值的较小值链表首地址
        }
        else if(list1->val<list2->val)
        {
            if(list3==NULL)
            {
                tail=list3=list1;   //如果新链表没有头则把较小值的地址赋值
            }
            else
            {
                list3->next = list1;
                list3=list3->next;
            }
            list1=list1->next;
        }
        else                //两值相同则赋值其中一个链表的首地址
        {
            if(list3==NULL)
            {
                tail=list3=list1;   //如果新链表没有头则把较小值的地址赋值
            }
            else
            {
                list3->next = list1;
                list3=list3->next;
            }
            list1=list1->next;
        }
    }   
    if(list1)       //其中一个表全部赋值完毕,侧再把另一个表的剩下值尾插到新表
    {
        list3->next=list1;
        return tail;
    } 
    else if(list2)
    {
        list3->next=list2;
        return tail;
    }
    else
    {
        return tail;
    }

}

到了这里,关于【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——链表OJ题

    目录   1.给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 2.给定一个带有头结点 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。 3.变形题:找到链表中倒数第k个

    2024年02月21日
    浏览(40)
  • 【数据结构初阶】链表OJ

    OJ 方案一: 题目解析: 方案二: 题目解析:把原链表遍历一遍,插入新链表 OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: OJ 题目解析: 定义快慢指针,使快指针先走与慢指针同步。然后同时走看是否相交 OJ 题目解析: OJ 题目解析:

    2024年02月05日
    浏览(50)
  • 数据结构——图解链表OJ题目

            学完了单链表之后,我们对其基本结构已经有了一定的了解,接下来我们通过一些题目强化对链表的理解,同时学习一些面试笔试题目的新思路以及加强对数据结构单链表的掌握。  目录 题目一.876. 链表的中间结点 - 力扣(LeetCode) 题目二:21. 合并两个有序链表

    2024年02月04日
    浏览(65)
  • 【数据结构OJ题】环形链表

    原题链接:https://leetcode.cn/problems/linked-list-cycle/description/ 目录 1. 题目描述 2. 思路分析 3. 代码实现 整体思路: 定义 快慢指针fast,slow ,如果 链表确实有环 , fast指针一定会在环内追上slow指针。 即慢指针一次走一步,快指针一次走两步,两个指针从链表起始位置开始运行,

    2024年02月12日
    浏览(41)
  • 【数据结构OJ题】链表分割

    原题链接:https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8tqId=11004rp=2ru=/activity/ojqru=/ta/cracking-the-coding-interview/question-ranking 目录 1. 题目描述 2. 思路分析 3. 代码实现 整体思路: 创建两个链表 ,分别存放 小于x的结点 和 大于等于x的结点 , 分别进行尾插 。 这道题目使

    2024年02月12日
    浏览(44)
  • 【数据结构与算法】手撕链表OJ题

    给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 思路一 :一种比较普遍的方式,边遍历边找不同。我们可以通过定义两个指针,一个指向头节点,一个置为NULL。当遇到值为相同的时候,直接跳过去。指向下一位

    2024年02月10日
    浏览(43)
  • 【数据结构OJ题】环形链表II

    原题链接:https://leetcode.cn/problems/linked-list-cycle-ii/description/ 如果有小伙伴不了解环形链表,可以先看看这篇文章: https://blog.csdn.net/m0_62531913/article/details/132352203?spm=1001.2014.3001.5502 我们来看下图:  我们根据这个结论就可以做出这道题目了!

    2024年02月12日
    浏览(43)
  • 【数据结构OJ题】移除链表元素

    原题链接:力扣  给你一个链表的头节点  head  和一个整数  val  ,请你删除链表中所有满足  Node.val == val  的节点,并返回 新的头节点  。  方法一:原地删除节点 思路:  首先,定义两个指针:prve和cur。它们会在遍历链表的过程中分别指向当前节点的前一个节点和当前

    2024年02月11日
    浏览(39)
  • 【数据结构与算法】:10道链表经典OJ

    思路1:遍历原链表,将 val 所在的节点释放掉。(太麻烦) 思路2:创建新链表,再遍历原链表,找到不为 val 的节点尾插到新链表。 思路1代码实现如下: 注意: 1.当链表为空时,直接返回NULL即可。 2.当尾插上最后一个有效节点时,此时它的 next 可能还与最后一个节点相链接,

    2024年04月14日
    浏览(38)
  • 【数据结构】--oj_合并两个有序链表(详解)

    目录 方法一:无头结点的方法  方法二:有头结点的方法 题述: 已给函数头: struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 已给出链表的结构体定义: struct ListNode {     struct ListNode* next;     int val; }; 已知l1、l2分别指向两个链表 要求: 将两个升序链表合并为一

    2024年02月07日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包