当前位置: 首页 > article >正文

【数据结构】_链表经典算法OJ(力扣/牛客第二弹)

目录

1. 题目1:返回倒数第k个节点

1.1 题目链接及描述

1.2 解题思路

1.3 程序

2. 题目2:链表的回文结构

2.1 题目链接及描述

2.2 解题思路

2.3 程序


1. 题目1:返回倒数第k个节点

1.1 题目链接及描述

题目链接:

面试题 02.02. 返回倒数第 k 个节点 - 力扣(LeetCode)

题目描述:

实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。

(该题目已保证给定k保证有效)

1.2 解题思路

思路1:计数转换为正数

遍历单链表计数,假设计得链表结点数为n,倒数第k个元素即正数第n-k个元素,再遍历返回第n-k个结点的值即可;

时间复杂度O(N)(但遍历链表两遍),空间复杂度O(1);

思路2:存储到数组中再下标访问正数元素

新创建一个数组,遍历单链表,依次将链表的结点值记录到数组中,假设计得链表结点数为n,结点值分别记录到数组下标0~n-1的位置,返回下标为n-k的数组元素值即可;

时间复杂度O(N),空间复杂度O(N);

思路3:快慢指针(本题解法)

创建两个指针,一个指针指向链表第一个结点,称为慢指针;一个指针指向链表第k个结点,称为快指针;

令两个指针同时向后遍历,直至快指针指向空时,此时慢指针即指向倒数第k个结点;

时间复杂度O(N)(只遍历链表一遍),空间复杂度O(1);

1.3 程序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {
    ListNode* fast=head,*slow=head;
    // 令fast先走k步
    while(k--){
        fast=fast->next;
    }
    // 快慢同时走
    while(fast){
        slow=slow->next;
        fast=fast->next;
    }
    return slow->val;
}

2. 题目2:链表的回文结构

2.1 题目链接及描述

题目链接:链表的回文结构_牛客题霸_牛客网

题目描述:

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

2.2 解题思路

思路1:

存储到数组,再创建两个计数变量分别从前向后和从后向前进行遍历来进行回文判断。

时间复杂度:O(N),空间复杂度:O(N)(不符合要求);

思路2:(本题解法)

第一步:定位链表的中间结点;

第二步:从中间结点开始,将链表的后半段逆置;

第三步:创建两个指针,一个指向链表第一个结点,一个指向链表的中间结点,两个同时向后走;

对于偶数个结点的链表,直至其中一个指针指向空即可对应匹配结束:

对于奇数个结点的链表,由于逆置的后半段链表并不影响原链表中间结点的的本来指向,未逆置的前半段链表的最后一个结点的指向其实还是指向原链表的结点,最终比较也是奇数个结点链表的中间结点的自我比较,匹配结束标志仍是任意一个指针指向空:

2.3 程序

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
using ListNode = struct ListNode;
class PalindromeList {
  public:
  // 查找中间结点
    struct ListNode* middleNode(struct ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
 // 逆置链表
    struct ListNode* reverseList(struct ListNode* head) {
        // 判空
        if (head == NULL) {
            return head;
        }
        // 创建三个指针
        ListNode* n1 = NULL;
        ListNode* n2 = head;
        ListNode* n3 = n2->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;

        }
        return n1;
    }
    // 判断回文
    bool chkPalindrome(ListNode* A) {
        // 查找中间链表
        ListNode* midNode=middleNode(A);
        // 逆置后半段链表
        ListNode* remidNode=reverseList(midNode);
        while(remidNode && A){
            if(remidNode->val != A->val){
                return false;
            }
            remidNode=remidNode->next;
            A=A->next;
        }
        return true;
    }
};

注:关于查找单链表中间结点、逆置链表的实现,在OJ相关文章有详解,文章链接如下:

【数据结构】_链表经典算法OJ(力扣版)-CSDN博客文章浏览阅读1.3k次,点赞33次,收藏21次。4、考虑特殊情况及相应处理:(1)原链表为空:即head=NULL,导致curNode=NULL,不会进入第一个while循环,但在newTail->next=NULL 时会导致空指针解引用操作,出现错误。故需对newTail是否为空进行单独讨论处理。(2)新链表为空:即原链表所有结点数据域的值都等于val,导致newTail->next=NULL 时会导致空指针解引用操作,出现错误。同(1):需对newTail是否为空进行单独讨论处理。处理逻辑为:https://blog.csdn.net/m0_63299495/article/details/145355272https://blog.csdn.net/m0_63299495/article/details/145355272


http://www.kler.cn/a/528452.html

相关文章:

  • 代码随想录——回溯
  • 《数据可视化新高度:Graphy的AI协作变革》
  • Spring MVC消息转换器
  • 如何对系统调用进行扩展?
  • 开启 AI 学习之旅:从入门到精通
  • AI-ISP论文Learning to See in the Dark解读
  • kamailio-auth模块详解【以下内容来源于官网,本文只做翻译】
  • ARM内核:嵌入式时代的核心引擎
  • 深度学习篇---数据存储类型
  • 机器学习优化算法:从梯度下降到Adam及其变种
  • 基于深度学习的输电线路缺陷检测算法研究(论文+源码)
  • FreeRTOS学习笔记2:FreeRTOS的基础知识
  • 42步进电机
  • FPGA| 使用Quartus II报错Top-level design entity ““ is undefined
  • 物联网 STM32【源代码形式-使用以太网】连接OneNet IOT从云产品开发到底层MQTT实现,APP控制 【保姆级零基础搭建】
  • Two Divisors ( Educational Codeforces Round 89 (Rated for Div. 2) )
  • 数字化转型导师坚鹏:AI大模型DEEPSEEK重构人工智能格局的里程碑
  • 小麦重测序-文献精读107
  • 简洁、方便是医疗控制设计的原则,背后的设计学和心理学依据
  • Day30-【AI思考】-12维错误类型 增强版解决方案库(含记忆钩子构建指南)