首页 > 其他分享 >数据结构初阶(2)——链表OJ

数据结构初阶(2)——链表OJ

时间:2024-08-21 23:22:12浏览次数:9  
标签:初阶 ListNode struct fast next 链表 while slow OJ

目录

1.面试题 02.02. 返回倒数第 k 个节点

2.OR36 链表的回文结构

3.160. 相交链表


1.面试题 02.02. 返回倒数第 k 个节点

思路:快慢指针,快指针先走k格,慢指针同步

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


int kthToLast(struct ListNode* head, int k){
    struct ListNode* fast,*slow;
    fast=slow=head;
    while(k--)
    {
        fast=fast->next;
    }
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
    return slow->val;
}

2.OR36 链表的回文结构

思路:先找中间节点,然后将节点后逆置,最后一一比较

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head)
    {
   struct ListNode* slow=head,*fast=head;
   while(fast&&fast->next)
   {
    slow=slow->next;
    fast=fast->next->next;
   }
   return slow;
    }
    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;
    }
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid=middleNode(A);
        struct ListNode* rmid=reverseList(mid);
        while(rmid&&A)
        {
            if(rmid->val!=A->val)
            return false;
            rmid=rmid->next;
            A=A->next;
        }
       return true;
    }
};

3.160. 相交链表

思路:先判断是否相交,再计算长度差值,再一一比较

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* cura=headA,*curb=headB;
    int lena=1,lenb=1;
    while(cura->next)
    {
        cura=cura->next;
        lena++;
    }
    while(curb->next)
    {
        curb=curb->next;
        lenb++;
    }
    if(cura!=curb)
    {
        return NULL;
    }
    int gap=abs(lena-lenb);
    struct ListNode* long1=headA,*short1=headB;
    if(lenb>lena)
    {
        long1=headB;
        short1=headA;
    }
    while(gap--)
    {
        long1=long1->next;
    }
    while(long1!=short1)
    {
        long1=long1->next;
        short1=short1->next;
    }
    return long1;
}

标签:初阶,ListNode,struct,fast,next,链表,while,slow,OJ
From: https://blog.csdn.net/2301_80065652/article/details/141397280

相关文章

  • 面试+算法之回文(Java):验证回文串、回文数、最长回文子串、回文链表、分割成回文串、
    概述算法是一个程序员的核心竞争力,也是面试最重要的考查环节。本文整理一些与回文相关的基础算法题。注:本文语言为Java。验证回文串如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个回文串。给定一个字符......
  • Project: Kill e
    接到上级任务,今天来暗杀\(e\)据说杀死\(e\)的方式就是把他算出来,好吧,现在我们还是来算一下考虑使用如下代数式求解\[e\\text{site:baidu.com}\]虽然我不知道这个代数式的意思是什么,但是我想他应该是某种高级的运算,特别是这个:看起来就像有什么神秘的力量考虑到我完全......
  • [lnsyoj2286/luoguP4458/BJOI2018]链上二次求和
    题意给定序列\(a\),要求支持修改与查询操作:修改操作为对区间\(l,r\)的每个数\(+d\),查询操作为给定区间\(l,r\),要求查询:\[\sum_{len=l}^r\sum_{i=l}^{n-len+1}\sum_{j=l}^{i+len-1}a_j\]sol化简式子(下设\(sum_i=\sum_{j=1}^ia_j,ssum_i=\sum_{j=1}^isum_j\)):\[\begin{al......
  • 数据结构-队列 c语言使用链表和数组分别实现
    队列定义队列(queue)是一种遵循先入后到规则的线性数据结构,将队列头部称为“队首”,尾部称为“队尾”,把元素加入队尾称为“入队”,删除队首元素称为“出队”。队列实现基于链表的实现将链表的头节点和尾结点分别视为“队首”和“队尾”,规定队尾仅可添加节点,队首仅可删除节点。......
  • 题解:UVA13026 Search the Khoj
    题意&翻译输入\(T\)组数据,每行数据有\(n\)个电话号码,最后再输入一行电话号码\(t\)。输出前面与\(t\)相差不超过一个字符的电话号码。思路把前面的\(n\)个电话号码逐个与\(t\)比较即可。ACcode#include<bits/stdc++.h>usingnamespacestd;intT,n;stringm[10......
  • TopoJSON格式详解,写入读取TopoJSON示例
    还是大剑师兰特:曾是美国某知名大学计算机专业研究生,现为航空航海领域高级前端工程师;CSDN知名博主,GIS领域优质创作者,深耕openlayers、leaflet、mapbox、cesium,canvas,webgl,echarts等技术开发,欢迎加底部微信(gis-dajianshi),一起交流。No.内容链接1Openlayers【入门教程】-......
  • 解决nvm ls-remote 列表只出现iojs版本
    前言在nvm安装node时发现显示不存在此版本,使用nvmls-remote查看可安装列表时发现,列表中只有iojs$nvmls-remoteiojs-v1.0.0iojs-v1.0.1iojs-v1.0.2iojs-v1.0.3iojs-v1.0.4iojs-v1.1.0iojs-v1.2.0iojs-v1.3.0iojs-v1.4.1......
  • 【数据结构与算法第一章】编程基础:变量与数据类型、指针、结构体、数组与链表、程序结
    目录【数据结构与算法第一章】编程基础1.1变量与数据类型1.2指针1.3结构体1.4数组和链表1.5程序结构1.6函数中参数的传递1.7C语言中运算符的含义【数据结构与算法第一章】编程基础1.1变量与数据类型变量:    ①在C语言中,所有变量必须先声明后使用......
  • 2.设计链表
    .-力扣(LeetCode)题意:在链表类中实现这些功能:get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。addAtTail(val):将值为 val的节点追加到链表的最......
  • 单链表C语言版
        一、单链表的定义单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。 程序如下:#include<stdio.h>#include<stdlib.h>//定义链表节点结构体typedefstructNode{intdata;//数据域structNode*nex......