浙江省建设厅网站张清云,网站开发国内外研究现状,学校网站模板图片,官网后台管理系统公主请阅 1. 返回倒数第 k 个节点1.1 题目说明1.2 题目分析1.3 解法一代码以及解释1.3 解法二代码以及解释 2.相交链表2.1 题目说明示例 1示例 2示例 3 2.2 题目分析2.3 代码部分2.4 代码分析 1. 返回倒数第 k 个节点 题目传送门 1.1 题目说明
题目名称#xff1a; 面试题 02… 公主请阅 1. 返回倒数第 k 个节点1.1 题目说明1.2 题目分析1.3 解法一代码以及解释1.3 解法二代码以及解释 2.相交链表2.1 题目说明示例 1示例 2示例 3 2.2 题目分析2.3 代码部分2.4 代码分析 1. 返回倒数第 k 个节点 题目传送门 1.1 题目说明
题目名称 面试题 02.02. 返回倒数第k个节点
题目要求 实现一种算法找出单向链表中倒数第 k 个节点并返回该节点的值。
注意 本题相对原题稍作改动。
示例 输入1 - 2 - 3 - 4 - 5 和 k 2 输出4
说明 给定的k保证是有效的。 1.2 题目分析
这个题的话需要我们将倒数第k个节点进行返回那么我们先想到的是什么呢怎么找打倒数第k个节点呢 解法一 那么这个时候我就想着将这个链表先逆置了然后遍历k次我们就可以找到原先链表的倒数第k个节点了 这个是一种解法
解法二 要解决这个问题我们可以使用 双指针又称为 快慢指针来找到链表中的倒数第 k 个节点。具体思路如下 初始化两个指针都指向链表的头节点。 快指针 fast慢指针 slow 移动快指针先让 fast 指针前进 k 步。 同时移动快慢指针当 fast 指针到达链表末尾时slow 指针的位置就是倒数第 k 个节点的位置。
详细步骤
定义 fast 和 slow 两个指针初始时都指向链表头部。让 fast 先走 k 步这样在之后的同时移动中fast 和 slow 之间的距离始终保持 k。然后同时移动 fast 和 slow每次 fast 向后移动一格直到 fast 到达链表的末尾。此时slow 就是倒数第 k 个节点。
那么下面我们会将两个解决方案的代码呈现出来的 1.3 解法一代码以及解释
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k)
{struct ListNode*prevNULL;struct ListNode*curhead;while(cur!NULL)//遍历整个链表,将链表反转了{struct ListNode*tmpcur-next;cur-nextprev;prevcur;curtmp;}//到这里prev就是反转链表的头结点了while(--k){prevprev-next;}return prev-val;
}//先将链表进行反转的操作然后我们就可以直接利用循环来找到第k个节点了先定义两个指针
-prev指向当前节点的前一个节点初始化为NULL
cur指向当前节点初始化为头结点
然后我们使用while循环进行遍历操作直到我们遍历到尾节点我们就结束了 我们先定义一个指针tmp将当前节点的下一个节点进行保存了 然后我们现在开始将相邻的两个节点的指向进行改变的操作了 我们让当前节点的下个节点指向我们的prev然后对prev这个指向进行更新现在指向了我们当前的节点了然后我们的cur也进行了更新了指向当前节点的下个节点了下个节点我们一开始使用tmp进行保存了然后我们直接进行赋值就行了 等循环结束了我们的链表的遍历操作就结束了那么就说明我们的链表已经逆置成功了那么现在我们的prev就是我们的头结点了 然后我们从这个头结点进行遍历操作我们遍历k次所以我们的循环条件是--k前置–返回的是-之前的值 等循环结束了我们的perv就是我们原先链表的倒数第k个节点了我们直接将这个节点的值进行返回就行了 1.3 解法二代码以及解释
int kthToLast(struct ListNode* head, int k){struct ListNode* first head;struct ListNode* last head;for(int i 1; i k ;i)first first-next;while(first-next){first first-next;lastlast-next;}return last-val;
}我们先创建了两个指针fast和last然后都初始化指向头结点但是我们让块指针先走k步然后我们继续使用while循环进行遍历操作但是是快慢指针一起进行遍历然后循环的条件就是快指针走到了尾节点的时候我们直接将尾节点的值进行返回就行了 但是这个原理是为什么呢
双指针法的原理可以通过以下几点进行解释 快慢指针之间的距离固定为 k 双指针法的核心思想是利用两个指针一个“快指针”fast和一个“慢指针”slow。我们首先让 快指针先走 k 步这样快指针和慢指针之间的距离就正好是 k。 同时移动快指针和慢指针 接下来当我们同时移动快慢指针时快指针每走一步慢指针也走一步。因为快指针最开始已经领先 k 步因此当快指针走到链表末尾时慢指针的位置就是倒数第 k 个节点。
具体来说假设链表的长度为 n当快指针走到末尾时它已经走了 n 步。而由于快指针最开始比慢指针多走了 k 步因此慢指针只走了 n - k 步此时 slow 就恰好指向倒数第 k 个节点。
保持链表的一次遍历 通过这种方式我们只需要遍历链表一次而不是两次就可以得到倒数第 k 个节点。相比于朴素方法先遍历链表得到链表长度再遍历到目标节点位置要遍历两次链表的时间复杂度双指针法将时间复杂度从 O(2n) 优化到了 O(n)。
总结原理
步数差快指针和慢指针在一开始保持 k 步的差距这样当快指针到达末尾时慢指针正好停在倒数第 k 个节点的位置。一次遍历只需要遍历链表一次就能完成任务避免了多次遍历的低效。指针同步移动当快指针到达链表末尾时慢指针正好位于我们想要的倒数第 k 个节点。 2.相交链表 题目传送门 2.1 题目说明
从图中提取的题目信息如下
题目描述 给你两个单链表的头节点 headA 和 headB请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点则返回 null。
注意
整个链表结构中不存在环。你不能更改链表的结构链表必须保持其原始结构。
示例 1 输入intersectVal 8, listA [4,1,8,4,5], listB [5,6,1,8,4,5], skipA 2, skipB 3
输出Intersected at 8示例 2 输入intersectVal 2, listA [1,9,1,2,4], listB [3,2,4], skipA 3, skipB 1
输出Intersected at 2示例 3 输入intersectVal 0, listA [2,6,4], listB [1,5], skipA 3, skipB 2
输出null输入参数
intersectVal相交的起始节点的值。如果不存在相交节点则该值为 0。listA链表 A。listB链表 B。skipA在链表 A 中从头节点开始跳到交叉节点的节点数。skipB在链表 B 中从头节点开始跳到交叉节点的节点数。
输出
如果链表相交返回相交的起始节点的值如果不相交返回 null。 2.2 题目分析
这个题给我们两个链表让我们找出两个链表的相交链表然后将相交节点进行返回的操作如果没有相交的节点的话我们直接返回NULL 那么这个题我们应该怎么进行设置呢 可能给的两个链的长度不一样啊那么我们应该怎么解决呢 我们可以找出长链然后计算出两个链的节点之差k然后让长链走k次那么我们的长链和短链就是同一个起点了然后一起进行遍历的操作边遍历边进行大小的比较的操作如果两个链表遍历的指针相遇了的话那么当前的指针所处的节点就是相交的节点了 那么思路就说到这里了下面就是我们的代码的实践了 2.3 代码部分
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///我们需要找到两个链表节点的差值//长链表先走差值数//两个链表开始遍历操作看看是不是同一个节点typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{if(headANULL||headBNULL){return NULL;}//创建两个指针分别指向A和B两个链表ListNode*l1headA;ListNode*l2headB;//计算两个链表的节点的个数int sizeA0,sizeB0;while(l1!NULL)//先遍历l1{sizeA;l1l1-next;}while(l2!NULL)//先遍历l1{sizeB;l2l2-next;}//求差值int gapabs(sizeA-sizeB);//绝对值//我们需要判断下谁是长链表//我们先假设ListNode*longlistheadA;ListNode*shortlistheadB;if(sizeAsizeB){longlistheadB;shortlistheadA;}//到这里我们就知道长短链表了while(gap--){longlistlonglist-next;}//上面的代码是找到长链表然后让长链表的指针走差值while(longlistshortlist)//两个链表不为空的话我们就往后面走{if(longlistshortlist)//说明相交了{return longlist;}//如果没有相交的话那么我们的两个指针接着走longlistlonglist-next;shortlistshortlist-next;}//到这里的话据说明没有相交的节点我们直接返回空就行了return NULL;}2.4 代码分析
我们先将特殊情况进行分析下如果两个链表都是空的话我们直接返回NULL就行了 然后我们就开始处理正常情况了 我们先创建两个指针分别指向我们的A和B两个链表分别是l1和l2指向对应链表的头结点 我们然后创建两个变量进行记录两个链表的头结点到尾节点的节点个数 然后我们就可以算出差值gap了然后我们进行长短链表的判断假设我们先假设长链表是A然后加链表是B如果sizeAsizeB的话那么长链表就是B,短链表就是A了 然后我们就可以将长短链表判断出来了 我们利用sizeAsizeB算出了节点差值 gap我们利用abs进行绝对值的操作 直到长链表是谁之后我们让长链表走gap次 走完之后我们的两个链表一起进行遍历使用while循环条件是两个链表不为空我们就往后走 然后在循环里面进行判断如果长链表的指针等于短链表的指针那么就说明两个指针相遇了那么这个节点就是我们想要的相交节点了 在这个条件判断之后我们进行两个指针的往后走一位的操作 如果出了循环还没有返回的话那么就说明这两个链表是不存在相交的节点的我们直接返回NULL就行了
