Leetcode链表题总结-编程实验室

一、链表介绍

链表是用一组位于任意位置的存储单元存储线性表的数据结构，这组存储单元可以是连续的，也可以不连续。
链表的操作有初始化、添加、遍历、插入、删除、查找等。

链表分为单向链表和双向链表。

使用链表时，可以直接用STL list,也可以自己写链表。如果自已写代码实现链表，有两种编码实现方法：动态链表、静态链表。

二、链表实现

数组模拟

单链表

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点inthead,e[N],ne[N],idx;// 初始化voidinit(){head=-1;idx=0;}// 在链表头插入一个数avoidinsert(inta){e[idx]=a,ne[idx]=head,head=idx++;}// 将头结点删除，需要保证头结点存在voidremove(){head=ne[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*dummy=newListNode(-1);dummy->next=head;ListNode*first=dummy;ListNode*second=dummy;for(inti=0;i<n;i++)first=first->next;while(first->next){first=first->next;second=second->next;}second->next=second->next->next;returndummy->next;}};

Lc 83.删除排序链表中的重复元素

leetcode
给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次_。
返回已排序的链表。

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

classSolution{public:ListNode*deleteDuplicates(ListNode*head){ListNode*h=head;for(;h;h=h->next){while(h->next&&(h->next->val==h->val))h->next=h->next->next;}returnhead;}};

lc206 反转链表

206. 反转链表 - 力扣（LeetCode）

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

解法1：迭代

首先创建一个头节点，然后按照顺序遍历链表，将链表中的每个节点插入头节点的后一个节点，当链表遍历完后返回头节点的后一个节点即可。

classSolution{public:ListNode*reverseList(ListNode*head){if(head==nullptr)returnhead;ListNode*h=newListNode(-1);ListNode*cur=head,*ne=head;while(ne!=nullptr){ne=ne->next;cur->next=h->next;h->next=cur;cur=ne;}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*tail=reverseList(head->next);head->next->next=head;head->next=nullptr;returntail;}};

lc92. 反转链表 II

1 将蓝色区域内的除了第一个结点所有链表结点反转，指针指向其前一个链表结点

2 修改反转区域的第一个结点和1号结点的指针指向
pre -> next -> next = pne; pre -> next = p;

实现

classSolution{public:ListNode*reverseBetween(ListNode*head,intleft,intright){if(!head||!head->next||left==right)returnhead;ListNode*dummy=newListNode(-1);dummy->next=head;ListNode*pre,*p,*pne;pre=dummy;for(inti=0;i<left-1;i++)pre=pre->next;p=pre->next;pne=p->next;for(inti=left;i<right&&pne;i++){ListNode*next=pne->next;pne->next=p;p=pne,pne=next;}pre->next->next=pne;pre->next=p;returndummy->next;}};

扩展：
25. K 个一组翻转链表 - 力扣（LeetCode）

lc141 环形链表

给你一个链表的头节点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*first=head,*second=first->next;while(first&&second){if(first==second)returntrue;first=first->next;second=second->next;if(second)second=second->next;}returnfalse;}};