141. 环形链表
题目描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
思路分析
如何判断是否有环?:快慢指针
分别定义fast和slow指针,分别指向头结点,fast每次移动两个节点,slow每次移动一个节点,如果fast和slow指针在途中相遇,则说明这个链表有环.
这个过程就如同操场跑步一样,跑的快的人在一段时间后就会追上慢的人.
参考代码
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode* next; ListNode() {} ListNode(int x):val(x),next(nullptr) { } ListNode(int x,ListNode* next):val(x),next(next) { } }; bool hasCycle(ListNode *head) { ListNode *slow = head,*fast = head; while(fast!=NULL){ fast = fast->next; if(fast!=NULL) { fast = fast->next; }else{//没有环 continue; } slow = slow->next; if(slow==fast){//有环 return true; } } return false;//没有环 }
142. 环形链表 II
题目描述
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null
解释：链表中没有环。
思路分析
本题主要考察:
- 判断链表是否环
- 如果有环，如何找到这个环的入口
如何判断是否有环?:快慢指针
分别定义fast和slow指针,分别指向头结点,fast每次移动两个节点,slow每次移动一个节点,如果fast和slow指针在途中相遇,则说明这个链表有环.
这个过程就如同操场跑步一样,跑的快的人在一段时间后就会追上慢的人.
如果有环，如何找到这个环的入口? ??
从头结点出发一个指针index1，从相遇节点 也出发一个指针index2，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
证明过程可以参考卡尔大佬的文章,讲的通俗易懂,嘿嘿嘿
参考代码
#include<bits/stdc++.h> using namespace std; struct ListNode { int val; ListNode* next; ListNode() {} ListNode(int x):val(x),next(nullptr) { } ListNode(int x,ListNode* next):val(x),next(next) { } }; ListNode *detectCycle(ListNode *head) { ListNode* slow = head,*fast= head,*index1,*index2; //首先判断有环没有环 while(fast!=NULL && fast->next!=NULL) { fast = fast->next->next;//fast走两步 slow = slow->next;//slow走一步 if(slow==fast) {//此时如果相遇必定是入口节点 index1 = head; index2 = slow; //寻找环的入口 while(index1!=index2) { index1 = index1->next; index2 = index2->next; } return index1; } } return NULL;//如果无环,则会退出while循环,返回NULL }
707. 设计链表
题目描述
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
思路分析
盲猜面试出这个的可能性很大,很考查基础.
示例：
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3 linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1-> 3 linkedList.get(1); //返回3
参考代码
#include<bits/stdc++.h> using namespace std; //很奇怪,按说是可以的... class MyLinkedList { public: //定义链表 struct LinkedNode { int val; LinkedNode* next; LinkedNode():val(0),next(NULL) { }; LinkedNode(int x):val(x),next(NULL) { }; LinkedNode(int x,LinkedNode* next):val(x),next(next) { }; }; MyLinkedList() { head = new LinkedNode(); size = 0; } //获取链表中 index 个节点的值。如果索引无效，则返回-1。 int get(int index) { if(index<0 || index> size-1 ) { return -1; } LinkedNode* cur = head->next; while(index--) { //实际上是获得index+1个节点 ,因为index是从0开始的 cur = cur->next; } return cur->val; } // 在链表头部添加节点。 void addAtHead(int val) { // ListNode *newNode = new ListNode(val,head->next); // head->next = newNode; head->next = new LinkedNode(val,head->next); size++; } //链表尾部添加节点 void addAtTail(int val) { LinkedNode* cur = head; while(cur->next) { cur = cur->next; } cur->next = new LinkedNode(val); size++; } //在链表中的第index个节点之前添加值为val 的节点。 //如果index等于链表的长度，则该节点将附加到链表的末尾 //如果 index 大于链表长度，则不会插入节点。 //如果index小于0，则在头部插入节点。 void addAtIndex(int index, int val) { if(index>size) { //如果 index 大于链表长度，则不会插入节点。 return; } if(index<0) { //如果index小于0，则在头部插入节点。 addAtHead(val); } if(index==size) { //如果index等于链表的长度，则该节点将附加到链表的末尾 addAtTail(val); } LinkedNode* cur = head; while(index--) { cur= cur->next; } cur->next = new LinkedNode(val,cur->next); // ListNode *newNode = new ListNode(val); // newNode->next = cur->next; // cur->next = newNode; size++; } //如果索引 index 有效，则删除链表中的第 index 个节点。 void deleteAtIndex(int index) { if(index>=size||index<0) { return; } LinkedNode* cur = head; while(index--) { cur = cur->next; } LinkedNode* temp = cur->next; cur->next = cur->next->next; delete temp; size--; } void printLinkedList(){ LinkedNode* cur = head; while(cur->next){ cout<<cur->next->val<<" "; cur = cur->next; } cout<<endl; } private: //全局变量 LinkedNode* head; int size ; }; int main() { MyLinkedList* obj = new MyLinkedList(); int param_1 = obj->get(0); cout<<param_1<<endl; obj->addAtHead(1); obj->printLinkedList(); obj->addAtTail(2); obj->printLinkedList(); obj->addAtIndex(1,3); obj->printLinkedList(); obj->deleteAtIndex(0); obj->printLinkedList(); return 0; }
备注:代码本身没啥问题,LeetCode关于这个题可能有点不严谨…
如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。
创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客
