首页 > 编程语言 >C语言简单的数据结构:单链表的有关算法题(1)

C语言简单的数据结构:单链表的有关算法题(1)

时间:2024-04-11 11:30:52浏览次数:27  
标签:head 单链 ListNode struct NULL next 链表 C语言 数据结构

算法题重点在于思路,代码其实并不难,这里的每一题都提供多种思路,大家可以动手写一下,并找到更好的解题方法
这里先介绍前三道

题目:

1.单链表相关经典算法OJ题1:移除链表元素

题目链接:https://leetcode.cn/problems/remove-linked-list-elements/description/
在这里插入图片描述
删除链表的指定元素
思路一:
在这里插入图片描述
让pcur找到要删除的元素,但是这样没法让链表连接,我们要在新建一个变量,来进行相连,还要有一个变量将pcur->next存下来,来释放pcur
在这里插入图片描述
在这里插入图片描述
思路二:
找值不为val的值然后将,尾插到新链表中
在这里插入图片描述
我们对这个方法进行代码实现:
在这里插入图片描述

此时运行
在这里插入图片描述
这里发现6并没有删除掉,原因就是5的节点仍然指向下一个节点
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
但这时又有问题了,我们对NULL指针进行解引用了,加一个判断如果newTail为NULL就部置NULL了
在这里插入图片描述
此时提交就通过了
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    // 创建新链表的头和尾
    ListNode* newHead = NULL;
    ListNode* newTail = NULL;

    ListNode* pcur = head;
    while (pcur) 
    {
        if (pcur->val != val) 
        {
            if (newHead == NULL) // 链表为NULL
            {
                newHead = newTail = pcur;
            } else 
            {
                newTail->next = pcur;
                newTail = newTail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newTail)
        newTail->next = NULL;
    return newHead;
}

2.单链表相关经典算法OJ题2:反转链表

题目链接:https://leetcode.cn/problems/reverse-linked-list/description/
在这里插入图片描述
思路一:
创建新链表,将原来的数据进行头插入
在这里插入图片描述

思路二:
创建3个指针完成原链表的反转
在这里插入图片描述
创建三个指针n3指向n1,然后三个指针都向后走,再加上部分NULL的判定即可
1.n3走到NULL时就不能向下走了
2.链表为NULL就不能运行直接返回
在这里插入图片描述
这里提交即可
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    //判空
    if(head == NULL)
    {
        return head;
    }
    ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)//如果n3不为NULL就继续向下
            n3 = n3->next;
    }
    return n1;
}

3. 单链表相关经典算法OJ题4:链表的中间结点

相关链接:https://leetcode.cn/problems/middle-of-the-linked-list/在这里插入图片描述
在这里插入图片描述
找到中间点,如果有两个中间点就是后一个
思路一:
遍历,count计算节点数,返回(count/2)的next节点
思路二:
快慢指针
创建两个指针让快指针刚好时慢指针的2倍,此时出现一下情况
在这里插入图片描述
思路理解了代码就好写了
在这里插入图片描述
在这里插入图片描述

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

多画图,多分析,多尝试写代码相信你会有所收获的,加油!!!

标签:head,单链,ListNode,struct,NULL,next,链表,C语言,数据结构
From: https://blog.csdn.net/2302_82004664/article/details/137623132

相关文章

  • C语言简单的数据结构:单链表
    目录:1.单链表的概念及结构2.单链表的实现2.1单链表的定义、创建和打印2.11单链表的定义2.12单链表的创建2.13单链表的打印2.2单链表的头插和尾插2.21尾插2.22头插2.3单链表的头删和尾删2.31尾删2.31头删2.4单链表的查找2.5单链表指定位置的插入和删除2.51指定位置前......
  • (Java)数据结构——排序(第一节)堆排序+PTA L2-012 关于堆的判断
    前言本博客是博主用于复习数据结构以及算法的博客,如果疏忽出现错误,还望各位指正。堆排序(HeapSort)概念堆排序是一种基于堆数据结构的排序算法,其核心思想是将待排序的序列构建成一个最大堆(或最小堆),然后将堆顶元素与最后一个元素交换,再将剩余元素重新调整为最大堆(或最小堆),重复......
  • C语言顺序表代码实现
    声明:著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。设计算法,实现线性结构上的顺序表的产生以及元素的查找、插入与删除,删除k个元素、有序表插入、元素逆置、2个有序表合并等。#include<stdio.h>#include<stdlib.h>//顺序表的定义:#defineListSiz......
  • C语言单链表代码实现
    声明:著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除,求表长、有序表插入、元素逆置、2个有序表合并等。#include<stdio.h>#include<stdlib.h>//单链表的定义:typedefintDataType......
  • 数据结构:单链表
    一.链表的概念及结构概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。但是在逻辑结构上是顺序的。链表的结构其实就像的火车:车厢是独立存在的,且每节车厢都有车门。想象⼀下这样的场景,假设每节车厢的车门都是锁......
  • C语言笔记二的补充(实例应用)——猜数游戏的简单实现
    猜数字游戏要求:电脑自动生成1~100的随机数玩家猜数字,猜数字的过程中,根据猜测数据的大小给出反馈,直至才对,游戏结束。基础知识搭建:随机数的生成使用rand函数intrand(void);rand函数会返回一个伪随机数,这个随机数的范围是在0~RAND_MAX之间,这个RAND_MAX的大小是依赖编......
  • C语言笔记二——分支和循环(上)
    分支和循环1.if语句1.1if语句的语法形式如下:if(表达式)语句表达式成立(为真)语句执行;表达式不成立(为假)语句不执行。在C语言中,0为假,非0为真。//instance#include<stdio.h>intmain(){  intnum=0;  scanf("%d",&num);  if(num%2==1){   ......
  • C语言: 字符串函数(下)
    片头在上一篇中,我们介绍了字符串函数。在这一篇章中,我们将继续学习字符串函数,准备好了吗?开始咯!1.strncpy函数1.1strncpy函数的用法strncpy是C语言中的一个字符串处理函数,它用于将一个字符串的一部分内容复制到另一个字符串中。其函数原型为:char*strncpy(char*dest......
  • 初识--数据结构
    什么是数据结构?我们为什么要学习数据结构呢....一系列的问题就促使我们不得不了解数据结构。我们不禁要问了,学习C语言不就够了吗?为什么还要学习数据结构呢?这是因为:数据结构能够解决C语言解决不了的问题,比如:图形,树状图...要了解数据结构,就必须要知道:数据,数据项,数据元素,数据对象,......
  • C语言分支和循环详解
    在程序中基础的三种结构为顺序结构,选择结构(分支结构),循环结构,几乎所有日常可见的事均可分为这三种结构或者这三种结构的组合.今天,我们就来详细了解一下关于C语言分支和循环语句.在正式介绍之前呢,先给大家提及一下C语言的控制语句:C语言共有9种控制语句,可以分为3类:......