算法刷题第五天(跑路人笔记)<双指针>

简介: 算法刷题第五天(跑路人笔记)<双指针>

第五天

链表的中间节点

image.png

876. 链表的中间结点 - 力扣(LeetCode)

使用快慢指针,fast指针一次走两个节点slow一次走一个节点.当fast或fast->next 走到NULL时我们的slow也就到了中间节点位置

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

删除链表的倒数第N个节点

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)

image.png

思路一(自己写法)

先遍历一遍数组得到数组长度然后通过数组长度和n(倒数第几的值)值相减的循环来得到使我们得到倒数第几的地址并我们先记录他上一个节点的地址最后处理特殊情况即可.

struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    if(head == NULL)
        return NULL;
    struct ListNode* cur = head;
    int len = 0;
    while(cur != NULL)
    {
        cur = cur->next;
        len++;
    }
    cur = head;
    struct ListNode* prev = head;
    for(int i = 0;i < len-n;i++)
    {
        prev = cur;//记录上一个节点
        cur = cur->next;
    }
    if(len == n)//解决删头节点问题
    {
        struct ListNode* tmp = head;
        head = head->next;
        free(tmp);
        return head;
    }
    if(prev == cur)//解决只有一个节点问题
    {
        free(cur);
        return NULL;
    }
    //正常情况
    prev->next = cur->next;
    return head;
}

官方解法可以避免if语句去处理特殊情况不过有一点点难理解.但是整体思路相同.


思路二(双指针)

双指针的思路其实也很简单通过两个指针先让快指针先走n个节点再让慢节点和快捷点一起走最终当快指针走到空时结束(注:我写的是fast->next==NULL时退出是为了让慢指针指向要删除的前一个节点方便我们后面的删除).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //头结点本身就为空
    if(head ==NULL)
    {
        return NULL;
    }
    //只有一个节点
    if(head->next == NULL)
    {
        free(head);
        return NULL;
    }
    for(int i =0;i<n;i++)//fast先走n步 
    {
        fast = fast->next;
    }
    while(fast != NULL&&fast->next != NULL)//fast!=NULL是为了防止删头结点.
    {
        slow = slow->next;
        fast = fast->next;
    }
    //fast为空只能是删头结点的时候
    if(fast == NULL)
    {
        struct ListNode* cur = head;
        head = head->next;
        free(cur);
        return head;
    }
    struct ListNode* tmp = slow->next;
    slow->next = tmp->next;
    free(tmp);
    return head;
}
相关文章
|
1月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
33 1
|
1月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
58 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
1月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
13 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
31 0
|
1月前
|
算法
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
❤️算法笔记❤️-(每日一刷-26、删除有序数组的重复项)
23 0
|
5月前
|
C语言
指针进阶(C语言终)
指针进阶(C语言终)
|
1月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
22 0
|
2月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
|
3月前
|
C语言
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
|
3月前
|
C语言
【C初阶——指针4】鹏哥C语言系列文章,基本语法知识全面讲解——指针(4)
【C初阶——指针4】鹏哥C语言系列文章,基本语法知识全面讲解——指针(4)