首页 > 其他分享 >攻克链表篇

攻克链表篇

时间:2024-07-18 20:56:02浏览次数:15  
标签:node head ListNode cur next 链表 攻克

leetcode206翻转链表

题目描述:

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1:

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2:

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

算法思想:

创建一个空链表头指针,将原给链表的节点依次遍历并采用头插法插入新创建的空链表头指针后完成翻转。

真正的草图哈哈哈!希望你能懂。没有官方的双指针快,但我觉得好理解一些,官方的双指针跟着画一遍图就能理解了。

算法实现:

ListNode* reverseList(ListNode* head) {
        //创建新的链——带头指针的
        ListNode *newList=new ListNode();
        while(head){
            //剥离当前指针指向的节点
            ListNode *node=head;
            head=head->next;
            node->next=nullptr;
            //第一个节点单独处理
            if(newList->next==nullptr) newList->next=node;
            //头插法插入
            else{
                node->next=newList->next;
                newList->next=node;
            }
        }
        //返回反转后的链表。注意这时候要把新链无意义的头节点去掉
        return newList->next;
    }

leetcode24——两两交换链表中的节点

题目描述:

给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。

示例 1:

输入:head = [1,2,3,4]
输出:[2,1,4,3]

示例 2:

输入:head = []
输出:[]

示例 3:

输入:head = [1]
输出:[1]

算法思想:

草图将就着看,哈哈哈。官解很牛有时间在钻研

算法实现:

ListNode* swapPairs(ListNode* head) {
        ListNode* cur=head;
        //若有交换返回node,因为在第一次交换后node变成了头
        ListNode* node=new ListNode();
        //flag标志着有没有进行交换
        int flag=0;
        //链表长度大于等于2才进行交换
        if(cur!=nullptr && cur->next!=nullptr){
            //第一种情况头节点的处理
            node=cur->next;
            cur->next=node->next;
            node->next=cur;
            flag=1;
            //其余节点的处理,有三个指针发生变化长度肯定要大于三
            while(cur && cur->next && cur->next->next){
                //动动小手画画图你随便理解
                ListNode* node1=cur->next;
                ListNode* node2=node1->next;
                cur->next=node1->next;
                node1->next=node2->next;
                node2->next=node1;
                cur=node1;
            }
        }
        if(flag) return node;
        else return head;
    }

标签:node,head,ListNode,cur,next,链表,攻克
From: https://blog.csdn.net/ch_ah/article/details/140530143

相关文章

  • 【算法】删除有序链表中的重复元素、保留重复节点的一个
    1.概述存在一个按升序排列的链表,给你这个链表的头节点head,请你删除所有重复的元素,使每个元素只出现一次。返回同样按升序排列的结果链表。本问题和【算法】删除有序链表中的重复元素、不保留重复节点很类似,但是思考起来稍微简单些,建议看完这个,看链接的这个吧。2.......
  • 基于Python语言的入门算法和数据结构(持续更新中,求关注一波)[链表 栈 队列 复杂度 操作]
    这篇文章主要是讲的Python语言的算法,本人还在不断记笔记中,文章也会持续更新,内容比较浅薄,请大家指教另外推荐一个比较好用的记笔记的软件Typora,自己已经使用很久了,感觉不错。。。虽然但是还是有欠缺。目录第一章算法概述1.1什么是数据结构?01数据结构都有哪些组成方式02......
  • 链表(3) ----快慢指针,求中间节点
    目录快慢指针算法步骤:为什么有效?使用场景:力扣876题目 方法代码 力扣142题目方法1代码 方法2 思路代码 官网地址:https://www.dhcode.cn/p/t_pc/goods_pc_detail/goods_detail/term_624bd804b3d39_Ac0g7V?fromH5=true&type=3&channel_id=&pro_id=term_62......
  • 【数据结构】队列:链表实现
    队列:链表实现结构描述:typedefintDataType;typedefstructQueueNode{DataTypeA;structQueueNode*Next;}Node;classQueueLinked{public://队头、队尾指针Node*Front;Node*Next;//队列操作//把元素X入队voidPush(Dat......
  • 【数据结构】循环队列:链表实现
    循环队列:链表实现结构描述typedefintDataType;typedefstructQueueNode{DataTypeA;structQueueNode*Next;}Node;classQueueCycLinked{public://队头、队尾指针Node*Front;Node*Next;//队列操作//把元素X入队voidPu......
  • 单链表
    单链表结构描述#include<iostream>#include<cstdlib>usingnamespacestd;typedefintDataType;//链表节点typedefstructNode{DataTypeA;structNode*Next;}Node;classSingleLinkedList{private:Node*Head;public://尾插......
  • 栈:链表实现
    栈:链表实现结构描述#include<iostream>#include<cstdlib>typedefintDataType;usingnamespacestd;typedefstructNode{DataTypeA;structNode*Next;}Node;classStackLinked{private:Node*Top;public:voidPush(DataTy......
  • 旋转链表-灵活运用取模
    题目描述:个人题解:        记给定链表的长度为n,注意到当向右移动的次数k≥n时,我们仅需要向右移动k%n次即可。因为每n次移动都会让链表变为原状。这样我们可以知道,新链表的最后一个节点为原链表的第(n−1)−(k%n)个节点(从0开始计数)。这样,我们可以先将给定......
  • 数据结构之细说链表
    1.1顺序表的问题以及思考经过上一篇顺序表的学习,我们知道顺序表还是有很多缺点顺序表的缺点:1.中间/头部的插入删除,实际复杂度为O(N)2.增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗3.扩容一般是呈两倍增长,势必会有一定的空间浪费。例如当前空间的容量是100,满了......
  • 数据结构——双链表与静态链表
    一、双链表1、定义 双链表:上一篇提到单链表,其实有一个弊端,就是只能单向读取,很笨重并且只能从头指针开始读取,而双链表是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点......