wordpress 视频站,手机自己做网站,wordpress prower,浅谈网站建设1.在一个排序的链表中#xff0c;存在重复的结点#xff0c;请删除该链表中重复的结点#xff0c;重复的结点不保留#xff0c;返回链表头指针 本题的意思是要删除链表中重复出现的节点#xff0c;然后返回删除重复节点后的链表。 我们可以直接用一个哨兵位以便于观察链表…1.在一个排序的链表中存在重复的结点请删除该链表中重复的结点重复的结点不保留返回链表头指针 本题的意思是要删除链表中重复出现的节点然后返回删除重复节点后的链表。 我们可以直接用一个哨兵位以便于观察链表的情况然后用前后指针来解决这个问题。如果当前节点cur的值与其当前节点的next的所存储的值相等且cur的next不为空cur就变成cur的next然后用while循环进行判断如果cur的val与cur的next的val相等且cur的next不为空就然后cur往后移动直到遇到不相同的情况跳出循环后cur还要记得移动到cur的next然后再将前指针prev的next置为cur这样就可以将相等的节点省略。当cur的next为空或者cur的值与cur的next的值不相等时就直接先将prev置为cur再将cur往后移动变成cur的next。最后返回哨兵位vpead的next就是存储了有效数据的首节点就可以返回整个删除后的单链表了。
完整代码如下
struct ListNode *deleteDuplication(struct ListNode *pHead)
{struct ListNode *vHead;vHead (struct ListNode *)malloc(sizeof(struct ListNode));vHead-next pHead;//定义虚头结点方便边界情况讨论struct ListNode *pre, *cur;pre vHead, cur pHead;while (cur){if (cur-next cur-val cur-next-val){cur cur-next;while (cur-next cur-val cur-next-val)cur cur-next;//当遇到与下一节点值相同时,cur推进到最后一个重复的数字处//本数字舍去,pre连接到下一个cur cur-next;pre-next cur;}//遇到与下一节点值不同或者是没有下一节点时,pre移动到此处,cur继续后移else if(!cur-next || cur-val ! cur-next-val){pre cur;cur cur-next;}}return vHead-next;
}2.对链表进行插入排序 本题也要使用到哨兵位用哨兵位的next最后可以返回排序完后的链表并且使用前后指针进行大小比较若是逆序则用前后指针的关系进行交换即可 完整代码如下
struct ListNode *insertionSortList(struct ListNode *head)
{if (head NULL) return head;struct ListNode *dummyHead malloc(sizeof(struct ListNode));dummyHead-val 0;dummyHead-next head;//哨兵位struct ListNode *lastSorted head;struct ListNode *curr head-next;while (curr ! NULL) {if (lastSorted-val curr-val) {lastSorted lastSorted-next;} else {struct ListNode *prev dummyHead;while (prev-next-val curr-val) {prev prev-next;}lastSorted-next curr-next;curr-next prev-next;prev-next curr;}curr lastSorted-next;}return dummyHead-next;
}3.给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 NULL 本题的意思很简单就是一个判断链表是否有环的问题如果有环就返回那个节点看图就明白了就是最后一个节点的next会连接到前面的节点就是有环。 到这里我们就要有一个大概的思路了–快慢指针 我们用慢指针slow一次走一步fast一次走两步到最后他们就一定会相遇因为他们移动的差距只有一步一次追一步就必然会相遇。当slow和fast相遇时我们再定义一个新指针从头节点开始往后移动同时将slow或者fast往后移动当这个新指针与slow或者fast相等时这个节点就返回这个节点这个节点就是链表尾链接到链表的节点。
完整代码如下
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode *slow head, *fast head;while (fast ! NULL) {slow slow-next;if (fast-next NULL) {return NULL;}fast fast-next-next;if (fast slow) {struct ListNode* ptr head;while (ptr ! slow) {ptr ptr-next;slow slow-next;}return ptr;}}return NULL;
}4.给定一个链表判断链表中是否有环 有了上一题的思路这一题就很简单了让slow指针和fast指针分别往后移动slow一次走一步fast一次走两步如果二者能相遇相遇即slow指针会与fast指针相等那就是链表中有环否则无环
完整代码如下
bool hasCycle(struct ListNode *head)
{struct ListNode* slowhead;struct ListNode* fasthead;while(fastfast-next){slowslow-next;fastfast-next-next;if(slowfast)return true;}return false;
}5.输入两个链表找出它们的第一个公共结点 其实这一题也很简单 首先我们得判断这个链表是否会相交如果相交那么两个链表的尾节点就会相等若不想等就直接返回NULL指针 其次我们分别求两个链表的长度用tail尾指针遍历求出lenA,lenB 然后我们用lenA-lenB相减的绝对值就能得出两个链表的长度差gap让长的链表先走gap步然后短的链表再和长的链表一起走当两个链表的指针节点相等时这个节点就是两个链表相遇的节点返回这个节点即可
完整代码如下
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* tailAheadA;struct ListNode* tailBheadB;int lenA1;int lenB1;while(tailA){tailAtailA-next;lenA;}while(tailB){tailBtailB-next;lenB;}if(tailA!tailB){return NULL;}int gapabs(lenA-lenB);struct ListNode* longlistheadA;struct ListNode* shortlistheadB;if(lenAlenB)//若长链表尾b则互换{longlistheadB;shortlistheadA; }while(gap--){longlistlonglist-next;}while(longlist!shortlist){longlistlonglist-next;shortlistshortlist-next;}return longlist;
}我们再OJ题的解题中可以发现快慢指针的解题思路是非常重要的大家可以多去做一点题 好了今天的分享到这里就结束了谢谢大家的支持
