坂田网站建设,wordpress静态规则,网站知识介绍,网站设计怎么好看在链表题目开始之前我们来复习一道数组元素的逆序问题#xff1a; 给定一个整数数组 nums#xff0c;将数组中的元素向右轮转 k 个位置#xff0c;其中 k 是非负数。
提示#xff1a;
1 nums.length 10^5-2^31 nums[i] 2^31 - 10 k 10^5 思… 在链表题目开始之前我们来复习一道数组元素的逆序问题 给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。
提示
1 nums.length 10^5-2^31 nums[i] 2^31 - 10 k 10^5 思路1旋转k次每一次项右轮转一个元素。时间复杂度O(N^2)。空间复杂度O(1)。 思路2创建一个新的数组现将原数组的后k个元素放置到新数组中然后再把剩余元素依次放入新数组中最后把新数组的元素按顺序放回原数组。时间复杂度O(N)。空间复杂度O(N)。
上面两种思路各有优势也有缺点。我们再来看看思路三。
思路3先逆序前n-k个元素再逆序后k个元素最后整体逆序。这种方法在时间、空间复杂度上都是最优的但是思路不好想到这就要大家多多积累我们来看看代码
void revese(int* nums,int left ,int right)
{while(left right){int tmp nums[left];nums[left] nums[right];nums[right] tmp;left;right--;}}void rotate(int* nums, int numsSize, int k)
{k % numsSize;revese(nums,0,numsSize-k-1);revese(nums,numsSize-k,numsSize-1);revese(nums,0,numsSize-1);
}
例1返回链表的倒数第k个节点 实现一种算法找出单向链表中倒数第 k 个节点。返回该节点的值。给定的 k 保证是有效的。 解 这到题的思路和之前的快慢指针相似我称之为先后指针我们先创建两个指针fast、slow既然是找倒数第k个节点那我们就先让fast走k个节点然后让两个指针同时向后走当fast指针走到尾节点时slow节点就是倒数第k个节点。代码如下
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k)
{ListNode* fast head;ListNode* slow head;while(k--){fast fast-next;}while(fast){fast fast-next;slow slow-next;}return slow-val;
} 例2链表的回文结构 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 解 这道题有些难度不过我们使用之前学的解法思路可以很轻松的过这道题。既然是回文结构那我们就先找到他的中间节点然后我们在逆序后半段链表然后再比较原头结点和逆序后的头结点的值如果不相等就返回false反之继续向后遍历直到其中有一个指针指向为空返回true。 bool chkPalindrome(ListNode* A) {//寻找中间节点struct ListNode * fast A;struct ListNode * slow A;while(fast fast-next){slow slow-next;fast fast-next-next;}//翻转后半链表:头插法struct ListNode* pcur slow;struct ListNode* newhead NULL;while(pcur){struct ListNode* next pcur-next;pcur-next newhead;newhead pcur;pcur next;}//向后遍历while(A newhead){if(A-val ! newhead-val){return false;}A A-next;newhead newhead-next;}return true;}
例3相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意函数返回结果后链表必须 保持其原始结构 。
提示
listA 中节点数目为 mlistB 中节点数目为 n1 m, n 3 * 10^41 Node.val 10^50 skipA m0 skipB n如果 listA 和 listB 没有交点intersectVal 为 0如果 listA 和 listB 有交点intersectVal listA[skipA] listB[skipB]
图示两个链表在节点 c1 开始相交 自定义评测
评测系统 的输入如下你设计的程序 不适用 此输入
intersectVal - 相交的起始节点的值。如果不存在相交节点这一值为 0listA - 第一个链表listB - 第二个链表skipA - 在 listA 中从头节点开始跳到交叉节点的节点数skipB - 在 listB 中从头节点开始跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点那么你的解决方案将被 视作正确答案 。 解 本道题在初见可能会没有思路因为我们没有办法确定他们是否相交了或者走到哪个节点了。但是仔细思考我们还是有办法去处理这些情况的。 首先我们要确定两个链表是否真的相交了那我们可以先遍历两个数组如果它们的尾节点为同一个说明它们是相交的反之即为不想交返回空指针。 如果是相交的话我们就要重新去寻找它们的第一个相交节点我们可以在第一次遍历判断他们是否相交时顺便计算一下两个链表的节点个数这样不需要重新再去计算降低了时间复杂度。如果A链表长那就让A先走len(A) - len(B)和节点然后让两个节点从所在位置继续向后遍历当两个节点相等时就找到了第一个相交节点返回该节点即可。 /*** 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)
{ListNode* cur1 headA;ListNode* cur2 headB;int len1 1;int len2 1;while(cur1-next){cur1 cur1-next;len1;}while(cur2-next){cur2 cur2-next;len2;}if(cur1 ! cur2){return NULL;}else{ListNode* pcur1 headA;ListNode* pcur2 headB;if(len1 len2){int num len1 - len2;while(num--){pcur1 pcur1-next;}}else{int num len2 - len1;while(num--){pcur2 pcur2-next;}}while(pcur1 ! pcur2){pcur1 pcur1-next;pcur2 pcur2-next;}return pcur1;}
} 例4随机链表的复制 给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。 例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。 返回复制链表的头节点。用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val,random_index] 表示
val一个表示 Node.val 的整数。random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。 解 本题的难点在于节点的随机指针random难以确定指向的方位。所以需要我们另辟蹊径我们可以直接在原链表的每个节点之后复制一个相同的节点这样我们就可以直到该新节点的随机节点的位置在原节点的随机节点的下一个位置。怎么样是不是很巧妙。 首先我们还是先判断原链表是否为空为空就返回NULL。反之我们就要开始插入复制节点了各位要注意新复制的原点的随机节点在第一遍遍历的时候都赋值为NULL因为第一遍还没有创建好所有的节点你可能找不到相应的随机节点。第二遍遍历就是单纯把所有的random都指向他们相应的节点。第三遍遍历为的是还原原链表并分离新链表。代码如下
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/
typedef struct Node Node;
Node* copyRandomList(Node* head)
{if (head NULL) return NULL;// 第一遍遍历在每个原节点后面插入复制节点struct Node *cur head;while (cur ! NULL) {struct Node *copyNode (struct Node *)malloc(sizeof(struct Node));//固定位置插入copyNode-val cur-val;copyNode-next cur-next;//随机指针先置为空后续节点完全创建好之后再进行复制copyNode-random NULL;cur-next copyNode;cur copyNode-next;}// 第二遍遍历设置复制节点的 random 指针cur head;while (cur ! NULL) {//NULL已经赋值过了所以无需再次复制if (cur-random ! NULL) {cur-next-random cur-random-next;}cur cur-next-next;}// 第三遍遍历将复制节点从原链表中分离出来//分离新链表的同时还原原链表cur head;struct Node *newHead head-next;struct Node *newCur newHead;while (cur ! NULL) {cur-next cur-next-next;if (newCur-next ! NULL) {newCur-next newCur-next-next;}cur cur-next;newCur newCur-next;}return newHead;
}
例5环形链表 给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
提示
链表中节点的数目范围是 [0, 10^4]-10^5 Node.val 10^5pos 为 -1 或者链表中的一个 有效索引 。 解 这道题不是很难但是用到了很多数理逻辑思维。首先我们要确定链表中是否存在环我们先假设有环那如何确定环的存在也是一个问题。我们来看一张图 我们依旧使用快慢指针来解题不了解的可以看前两篇文章。slow走一步fast走两步直到slow进入环中fast开始追击slow因为fast每次都比slow多走一步那是不是说明fast早晚都可以追上slow呀。既然能追上是不是就说明有环存在这道题就解了。如果没有环两个指针就不可能相遇我们在里面判断一下就可以了。代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head)
{//判断是否为空链表if(head NULL){return false;}ListNode* fast head;ListNode* slow head;//循环中如果fast和slow相等说明成环不成环在循环结束后会返回faslewhile(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){return true;}}return false;
}
例5拓展 我们要讨论的远远不止这些如果slow固定为走一步但是fast不是走两步而是走三步、四步、五步……呢下面我们来一个一个讨论 我们假设进环前的节点个数为L环的节点个数为C当slow进环时fast与slow相距N。 我们先来看fast走三步的情况 每移动一次指针fast和slow的距离就会减少2如果N为偶数过程为N、N-2、N-4、……、2、0最后两个指针会相遇如果N为奇数过程为N、N-2、N-4、……、3、1、-1我们会发现两个指针错过了并且越来越远我们就需要重新计算它们的距离。错过之后它们的距离变成了C-1当C-1为偶数时它们最终会相遇对吧但是当C-1为奇数时它们就永远不会相遇了。那这里是不是就无解了呢我们继续往下去探讨 我们假设slow走的路程是L那么fast走的就是L x*C C-Nx为正整数。我们还知道fast走的路程是slow的三倍那么我们就可以写出关系式3L L x*C C-N。化简之后我们可以得到2L (x1)*C -N。由于C-1是奇数仔细看你会发现偶数 任意整数 * 偶数 - 奇数。这是一个恒不成立的等式也就是说这种情况不存在。那我们是不是就可以证明fast必定可以追上slow。 看完三步后我们再来看看四步的每移动一次指针fast和slow的距离就会减少3这时我们要分三种情况去看N%30时过程为N、N-3、N-6、……、3、0可以相遇N%31时过程N、N-3、N-6、……、4、1、C-2当N%32时过程为N、N-3、N-6、……、5、2、C-1。后面的过程和三步的相似各位感兴趣可以自己去算一下这里不过多着笔。 从这两种情况中我们要学的是数理逻辑思维在正式工作时很少用到但是在面试时可能会被问大家注意一下就可以了。
例6环形链表二 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
提示
链表中节点的数目范围在范围 [0, 10^4] 内-10^5 Node.val 10^5pos 的值为 -1 或者链表中的一个有效索引 解 这道题用上面的思路可以很快就解决 我们使用两步fast的快慢指针来解决。 首先我们让fast和slow走到相遇节点记为meet。我们来算一下假设slow走了LN fast走了L x*C N。由关系可得2(LN) L x*C N。化简得L (x-1)*C C-N。其中C是环的节点数C-N就是meet到入环节点的距离因为x-1是可以等于0的我们惊喜地发现L C-N。也就是说在头指针和meet一起向后走会同时到达我们要的节点。代码如下
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
ListNode *detectCycle(struct ListNode *head)
{ListNode* fast head;ListNode* slow head;ListNode* meet NULL;//相遇while(fast fast-next){slow slow-next;fast fast-next-next;if(fast slow){meet fast;break;}}//判断链表是否无环if(fast NULL || fast-next NULL){return NULL;}//返回入环的第一个节点ListNode* pcur head;while(pcur ! meet){pcur pcur-next;meet meet-next;}return meet;}
