＜代码随想录二刷＞链表

＜代码随想录二刷＞链表

文章目录

​​203. 移除链表元素​​

​​题目描述​​​​思路分析​​​​参考代码​​

​​206. 反转链表​​

​​题目描述​​​​思路分析​​​​参考代码​​

​​24. 两两交换链表中的节点​​

​​题目描述​​​​思路分析​​​​参考代码​​

​​19. 删除链表的倒数第 N 个结点​​

​​题目描述​​​​思路分析​​​​参考代码​​

​​面试题 02.07. 链表相交​​

​​题目描述​​​​思路分析​​​​参考代码​​

​​141. 环形链表​​

​​题目描述​​​​思路分析​​​​参考代码​​

​​142. 环形链表 II​​

​​题目描述​​​​思路分析​​​​参考代码​​

​​707. 设计链表​​

​​题目描述​​​​思路分析​​​​参考代码​​

203. 移除链表元素

​​题目描述​​

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

输入：head = [1,2,6,3,4,5,6], val = 6输出：[1,2,3,4,5]

示例 2：

输入：head = [], val = 1输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7输出：[]

思路分析

双指针

先为原始链表创建一个虚拟头结点(便于操作),然后定义两个指针,pre指向前一个节点,cur指向当前节点.

当前节点满足条件,则进行移除操作.

最后删除创建的虚拟头结点.

图解过程:

参考代码

#includeusing namespace std;struct ListNode { int val; ListNode* next; ListNode():val(0),next(nullptr) {} ListNode(int x):val(x),next(nullptr) {} ListNode(int x,ListNode* next):val(x),next(nullptr) {}};//采用双指针ListNode* removeElements(ListNode* node, int val) { ListNode* head = new ListNode(-1,node) ;//定义头结点 ListNode* pre = head;//初始化 ListNode* cur = head->next;//这里也可以直接使用一个cur变量来删除节点,我们定义两个,逻辑更加清晰 ListNode* temp; while(cur!=NULL) { if(cur->val==val) { temp = cur; pre->next = cur->next; cur = cur->next; delete temp; } else { pre = cur; cur = cur->next; } } //删除虚拟头结点 temp = head->next; delete head; return temp;}

206. 反转链表

​​题目描述​​

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = []输出：[]

思路分析

方法一：双指针

基本思路:从前往后将指针的方向改变,返回最后一个节点 使用pre指向前一个节点,cur代表当前节点,从第一个节点开始进行遍历,每次让cur指向pre,之后cur继续遍历下一个节点,直至链表遍历完毕.

方法二：递归（从前往后改变指针方向）

思路和方法一基本一致,递归实际上就是自己调用自己,每次的操作一致.

每次我们需要改变指针指向,需要操作两个节点,当前节点cur和上一个节点pre,所以这就是递归函数的参数.递归的结束条件就是当前节点为NULL,则不再需要改变方向了.递归结束.

方法三：递归（从后往前改变指针方向）

参考代码

方法一：双指针

//方法一:双指针法ListNode* reverseList(ListNode* head) { if(head==NULL||head->next==NULL) { //判断0个和1个节点情况,不用进行反转 return head; } ListNode *pre = NULL,*cur = head,*temp = head->next; //开始 从前往后改变指针的指向 while(cur) { temp = cur->next;//保存下一个节点 cur->next = pre;//改变指向 pre = cur;//pre后移动 cur = temp; //cur后移动 } return pre;}

方法二：递归(从前往后改变指针方向)

//方法二:递归法1 先改变指针方向,再继续进行递归ListNode* reverse(ListNode* pre,ListNode* cur) {//返回值主要是用来递归完成之后返回头结点的,无其他用途 if(cur==NULL) { return pre; } ListNode* temp = cur->next; cur->next = pre;//修改指针方向 return reverse(cur,temp) ;}ListNode* reverseList(ListNode* head) { if(head==NULL||head->next==NULL) { //判断0个和1个节点情况,不用进行反转 return head; } return reverse(NULL,head);}

方法三：递归（从后往前改变指针方向） 目前测试不通过…

//方法三:递归法2 先进行递归,后改变指针方向 -不知道为啥错了.. ListNode* resNode = new ListNode(-1);ListNode* solve(ListNode* cur) { if(cur==NULL) { //结束条件 return resNode; } ListNode* pre = solve(cur->next); pre->next = cur; return cur;}ListNode* reverseList(ListNode* head) { if(head==NULL||head->next==NULL) { //判断0个和1个节点情况,不用进行反转 return head; } solve(head); ListNode* head = resNode->next; delete resNode; return head;}

24. 两两交换链表中的节点

​​题目描述​​

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

示例 2：

输入：head = []输出：[]

示例 3：

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

思路分析

题目的要求是交换相邻的节点,题目也说了是这两个节点的顺序发生改变,而不是仅仅交换下值.而且如果当前节点只有一个,则肯定不需要交换啦.

接下来我们用图解来表示:

根据图中,我们可以使用三个辅助变量便可完成操作.

参考代码

#includeusing 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* swapPairs(ListNode* head) { if(head==NULL||head->next==NULL){//没有结点或者只有一个结点时 return head; } ListNode* dummyHead = new ListNode(-1,head);//创建虚拟头结点 ListNode *cur = dummyHead,*node1,*node2,*node3;//创建当前节点cur以及辅助节点node1、node2、node3 while( cur->next && cur->next->next){ node1 = cur->next; node2 = cur->next->next; node3 = cur->next->next->next; cur->next = node2;//执行第一步:当前0节点指向2号节点 node2->next = node1;//执行第二步:当前2节点指向1号节点 node1->next = node3;//执行第三步:当前1节点指向3号节点. cur = node1;//更新cur } head = dummyHead->next; delete dummyHead; return head;}

19. 删除链表的倒数第 N 个结点

​​题目描述​​

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

示例 2：

输入：head = [1], n = 1输出：[]

示例 3：

输入：head = [1,2], n = 1输出：[1]

思路分析

方法一:逆向思维法

删除倒数第n个节点 ==> 删除正数N-n+1个节点.

图解:(以实例一为例)

方法一:快慢指针 先搞一个虚拟头结点,方便我们接下来的操作.

第一步slow和fast都指向虚拟头结点.第二步fast向前移动n+1个节点slow和fast同时向前移动,直至fast为空,则slow对应的便是目标节点的前一个节点.

图解

参考代码

方法一:逆向思维法

//方法一:逆向思维法 删除倒数第n个节点 ==> 删除正数N-n+1个节点. ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummyHead = new ListNode(-1,head); ListNode *cur,*temp; cur = dummyHead->next; int N = 0,m;//总结点 while(cur) { N++; cur=cur->next; } //删除第n个节点 m = N-n; cur = dummyHead; while(m--){//指针指向第m个位置 cur=cur->next; } temp = cur->next;//保存删除节点 cur->next = cur->next->next;//进行删除 delete temp;// delete dummyHead; head = dummyHead->next; //最后的head一定要重新赋值哦,因为之前的head 可能已经挂了. delete dummyHead; return head;}

方法二:双指针法

//方法二:双指针法(快慢指针法) ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *dummyHead = new ListNode(-1,head); ListNode *slow = dummyHead,*fast = dummyHead,*temp; //fast先走n+1步 while(n>=0) { fast = fast->next; n--; } //slow和fast同时开始走,直到fast为NULL while(fast!=NULL) { slow = slow->next; fast = fast->next; } //进行删除 temp = slow->next; slow->next = slow->next->next; delete temp; head = dummyHead->next; delete dummyHead; return head;}

面试题 02.07. 链表相交

​​题目描述​​

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。

思路分析

题目的要求是求两个链表的交点,但是这里的交点是指针相等,不是节点里面的值相同.

看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点,如何求得交点呢.

我们可以求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：

此时我们就可以让CurA和CurB,从前往后遍历各自链表的节点,直到两者相等,此时对应的便是交点. 如果两个链表都遍历完还没有找到,则说明没有交点.

参考代码

#includeusing 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 *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode *pointerA = headA,*pointerB = headB; int lenA = 0,lenB = 0,gap;//a:b代表两条链表的长度 while(pointerA) {//求LenA长度 lenA++; pointerA = pointerA->next; } while(pointerB) {//求LenB长度 lenB++; pointerB = pointerB->next; } 始终让A的长度比B大 if(lenA>lenB) { pointerA = headB; pointerB = headA; gap = lenA-lenB; }else{ pointerA = headA; pointerB = headB; gap = lenB-lenA; } while(gap--) {//B指针移动到和A指针相同的位置 pointerB = pointerB->next; } while(pointerA&&pointerB) {//A和B一起向前移动 if(pointerA==pointerB){//如果相同则直接进行返回 return pointerA; } pointerA = pointerA->next; pointerB = pointerB->next; } return NULL;//如果没有公共结点,则返回NULL; }

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指针在途中相遇,则说明这个链表有环.

这个过程就如同操场跑步一样,跑的快的人在一段时间后就会追上慢的人.

参考代码

#includeusing 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

解释：链表中没有环。

思路分析

本题主要考察:

判断链表是否环如果有环，如何找到这个环的入口

如何判断是否有环?:快慢指针

分别定义fast和slow指针,分别指向头结点,fast每次移动两个节点,slow每次移动一个节点,如果fast和slow指针在途中相遇,则说明这个链表有环.

这个过程就如同操场跑步一样,跑的快的人在一段时间后就会追上慢的人.

从头结点出发一个指针index1，从相遇节点 也出发一个指针index2，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

​​证明过程可以参考卡尔大佬的文章,讲的通俗易懂,嘿嘿嘿​​

参考代码

#includeusing 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-> 3linkedList.get(1); //返回2linkedList.deleteAtIndex(1); //现在链表是1-> 3linkedList.get(1); //返回3

参考代码

#includeusing 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<next->val<<" "; cur = cur->next; } cout<get(0); cout<addAtHead(1); obj->printLinkedList(); obj->addAtTail(2); obj->printLinkedList(); obj->addAtIndex(1,3); obj->printLinkedList(); obj->deleteAtIndex(0); obj->printLinkedList(); return 0;}

备注:代码本身没啥问题,LeetCode关于这个题可能有点不严谨…

如果有收获！！！ 希望老铁们来个三连，点赞、收藏、转发。 创作不易，别忘点个赞，可以让更多的人看到这篇文章，顺便鼓励我写出更好的博客

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。