Leetcode链表题总结

一、链表介绍链表是用一组位于任意位置的存储单元存储线性表的数据结构这组存储单元可以是连续的也可以不连续。链表的操作有初始化、添加、遍历、插入、删除、查找等。链表分为单向链表和双向链表。使用链表时可以直接用STL list,也可以自己写链表。如果自已写代码实现链表有两种编码实现方法动态链表、静态链表。二、链表实现数组模拟单链表// head存储链表头e[]存储节点的值ne[]存储节点的next指针idx表示当前用到了哪个节点inthead,e[N],ne[N],idx;// 初始化voidinit(){head-1;idx0;}// 在链表头插入一个数avoidinsert(inta){e[idx]a,ne[idx]head,headidx;}// 将头结点删除需要保证头结点存在voidremove(){headne[head];}结构体实现单链表//Definition for singly-linked list.structListNode{intval;ListNode*next;ListNode():val(0),next(nullptr){}ListNode(intx):val(x),next(nullptr){}ListNode(intx,ListNode*next):val(x),next(next){}};三、链表基础操作总结leetcode提供的链表一般没有头结点某些题目需要注意添加头结点这样一来我们就不需要对链表的第一个结点进行特殊的操作与判断了。Lc 19.删除链表的倒数第N个结点leetcode给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。方法快慢指针由于我们需要找到倒数第 n 个节点因此我们可以使用两个指针 first 和 second 同时对链表进行遍历并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时second 就恰好处于倒数第 n 个节点的前一个节点。classSolution{public:ListNode*removeNthFromEnd(ListNode*head,intn){ListNode*dummynewListNode(-1);dummy-nexthead;ListNode*firstdummy;ListNode*seconddummy;for(inti0;in;i)firstfirst-next;while(first-next){firstfirst-next;secondsecond-next;}second-nextsecond-next-next;returndummy-next;}};Lc 83.删除排序链表中的重复元素leetcode给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次_。返回 已排序的链表 。链表中节点数目在范围 [0, 300] 内-100 Node.val 100题目数据保证链表已经按升序 排列classSolution{public:ListNode*deleteDuplicates(ListNode*head){ListNode*hhead;for(;h;hh-next){while(h-next(h-next-valh-val))h-nexth-next-next;}returnhead;}};lc206 反转链表206. 反转链表 - 力扣LeetCode给你单链表的头节点 head 请你反转链表并返回反转后的链表。解法1迭代首先创建一个头节点然后按照顺序遍历链表将链表中的每个节点插入头节点的后一个节点当链表遍历完后返回头节点的后一个节点即可。classSolution{public:ListNode*reverseList(ListNode*head){if(headnullptr)returnhead;ListNode*hnewListNode(-1);ListNode*curhead,*nehead;while(ne!nullptr){nene-next;cur-nexth-next;h-nextcur;curne;}returnh-next;}};解法2递归首先我们先考虑 reverseList 函数能做什么它可以翻转一个链表并返回新链表的头节点也就是原链表的尾节点。所以我们可以先递归处理 reverseList(head-next)这样我们可以将以head-next为头节点的链表翻转并得到原链表的尾节点tail此时head-next是新链表的尾节点我们令它的next指针指向head并将head-next指向空即可将整个链表翻转且新链表的头节点是tail。classSolution{public:ListNode*reverseList(ListNode*head){if(!head||!head-next)returnhead;ListNode*tailreverseList(head-next);head-next-nexthead;head-nextnullptr;returntail;}};lc92. 反转链表 II1 将蓝色区域内的除了第一个结点所有链表结点反转指针指向其前一个链表结点2 修改反转区域的第一个结点和1号结点的指针指向pre - next - next pne; pre - next p;实现classSolution{public:ListNode*reverseBetween(ListNode*head,intleft,intright){if(!head||!head-next||leftright)returnhead;ListNode*dummynewListNode(-1);dummy-nexthead;ListNode*pre,*p,*pne;predummy;for(inti0;ileft-1;i)prepre-next;ppre-next;pnep-next;for(intileft;irightpne;i){ListNode*nextpne-next;pne-nextp;ppne,pnenext;}pre-next-nextpne;pre-nextp;returndummy-next;}};扩展25. K 个一组翻转链表 - 力扣LeetCodelc141 环形链表给你一个链表的头节点head判断链表中是否有环。如果链表中存在环 则返回true。 否则返回false。暴力根据题目规定的链表最大长度决定while循环的最大次数循环次数超标说明链表存在环。class Solution { public: bool hasCycle(ListNode *head) { int len 0; while(head) { head head - next; len ; if(len 1e4) return true; } return false; } };双指针用两个指针从头开始扫描第一个指针每次走一步第二个指针每次走两步。如果走到 null说明不存在环否则如果两个指针相遇则说明存在环。假设链表存在环则当第一个指针走到环入口时第二个指针已经走到环上的某个位置距离环入口还差 x步。由于第二个指针每次比第一个指针多走一步所以第一个指针再走 x步两个指针就相遇了时间复杂度分析第一个指针在环上走不到一圈所以第一个指针走的总步数小于链表总长度。而第二个指针走的路程是第一个指针的两倍所以总时间复杂度是 O(n)。classSolution{public:boolhasCycle(ListNode*head){if(!head||!head-next)return0;ListNode*firsthead,*secondfirst-next;while(firstsecond){if(firstsecond)returntrue;firstfirst-next;secondsecond-next;if(second)secondsecond-next;}returnfalse;}};