提交网站收录,网站制作用的软件有哪些,网站域名注册免费,免费自学编程100例目录
一、移除链表元素
二、找出链表的中间节点
三、合并两个有序链表
四、反转链表
五、求链表中倒数第k个结点
六、链表分割
七、链表的回文结构
八、判断链表是否相交
九、判断链表中是否有环(一)
十、 判断链表中是否有环(二) 注#xff1a;第六题和第七题牛…目录
一、移除链表元素
二、找出链表的中间节点
三、合并两个有序链表
四、反转链表
五、求链表中倒数第k个结点
六、链表分割
七、链表的回文结构
八、判断链表是否相交
九、判断链表中是否有环(一)
十、 判断链表中是否有环(二) 注第六题和第七题牛客没有C环境我在C环境下用C语言写这道题目前还没学C请大佬们理解一下理解万岁
一、移除链表元素
203. 移除链表元素 - 力扣LeetCode 给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 示例 1 输入head [1, 2, 6, 3, 4, 5, 6], val 6
输出[1, 2, 3, 4, 5]struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* prev NULL, * cur head;while (cur) { if (cur-val val) {if (prev) {prev-next cur-next;free(cur);cur prev-next;}else {cur head-next;free(head);head cur;}}else {prev cur;cur cur-next;}}return head;
} 思路链表常规删除注意删除头节点的情况。 1、创建指向当前节点的前一个节点的指针prevNULL头节点的前一个节点为空指针cur指向链表头节点。 2、以当前节点cur不为空为循环执行条件判断当前节点的值是否等于val等于则进行删除不等于则prev更新为当前节点cur当前节点cur指向下一个节点。 3、当前节点的值等于val时 如果值为 val 的节点不在头节点prev 不为 NULL将 prev 的 next 指针指向当前节点的下一个节点然后释放当前节点并更新。如果值为 val 的节点在链表头节点prev 为 NULL则释放原来的头节点将 head 更新为当前节点的下一个节点。 下面是第二种方法创建新的链表把不删除的节点链接到新链表 struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* cur head; // 当前遍历节点struct ListNode* newhead NULL; // 新链表的头节点struct ListNode* tail NULL; // 新链表的尾节点while (cur) {if (cur-val ! val) { // 当前节点的值不等于要删除的值if (tail NULL) { // 第一次插入newhead tail cur; // 设置新链表的头和尾}else {tail-next cur; // 将当前节点连接到新链表的尾部tail tail-next; // 更新新链表的尾节点}cur cur-next; // 移动到下一个节点tail-next NULL; // 断开新链表的尾节点连接}else {struct ListNode* del cur; // 保存需要删除的节点cur cur-next; // 移动到下一个节点free(del); // 释放需要删除的节点的内存}}return newhead; // 返回新链表的头节点已移除所有值为 val 的节点
}二、找出链表的中间节点
876. 链表的中间结点 - 力扣LeetCode 给你单链表的头结点 head 请你找出并返回链表的中间结点。 如果有两个中间结点则返回第二个中间结点。 示例 1 输入head [1,2,3,4,5]输出[3,4,5]解释链表只有一个中间结点值为 3 。 struct ListNode* middleNode(struct ListNode* head) {struct ListNode* fast head, * slow head;while (fast fast-next) {slow slow-next;fast fast-next-next;}return slow;
} 思路快慢双指针 1、采用速度为1步的slow和速度为2步的fast这样设置二者速度比较合理。 2、循环结束的条件需要考虑一下分为链表节点个数为奇数和偶数当fast走到最后的结果如下 3、 所以循环结束的条件为 fast fast-next 二者有一个为空。 三、合并两个有序链表
21. 合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1 输入l1 [1,2,4], l2 [1,3,4]
输出[1,1,2,3,4,4]struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 NULL)return list2;if (list2 NULL)return list1;struct ListNode* tail NULL, * head NULL;while (list1 list2) {if (list1-val list2-val) {if (tail NULL) {head tail list1;}else {tail-next list1;tail tail-next;}list1 list1-next;}else {if (tail NULL) {head tail list2;}else {tail-next list2;tail tail-next;}list2 list2-next;}}if (list1)tail-next list1;if (list2)tail-next list2;return head;
} 思路创建新链表较小的进行链接。
好像跟顺序表的题相像合并两个有序数组
不过这次是单链表所以我们可以创建新链表从前向后将较小的链接到链表中不需要从后先前了。 1、首先判断是否有链表为空一个链表为空则直接返回合并后的结果另一个不为空的链表都为空则返回任意一个链表。 2、创建新链表的尾节点tail和头节点head初始化为空。 3、比较 list1 和 list2 当前节点的值。 如果 list1 的当前节点值小于 list2 的当前节点值将 list1 的节点添加到合并后的链表中。如果 list2 的当前节点值小于等于 list1 的当前节点值将 list2 的节点添加到合并后的链表中。 4、在向合并链表中添加节点时需要检查 tail 是否为 NULL 如果是说明这是第一个节点因此同时更新 head 和 tail。否则只需将新节点连接到 tail 的 next 并将 tail 更新为新节点。 5、每次添加节点后对应的链表list需要向后移动一位。 6、最终循环结束时如果有链表不为空证明该链表剩余节点的值均大于另一个链表的最大值则将该链表其余的节点依次插入新链表。 7、返回新链表头节点head。 四、反转链表
206. 反转链表 给你单链表的头节点 head 请你反转链表并返回反转后的链表。 示例 1 输入head [1,2,3,4,5]
输出[5,4,3,2,1] struct ListNode* reverseList(struct ListNode* head) {struct ListNode* cur head;struct ListNode* rhead NULL;while (cur) {struct ListNode* next cur-next;cur-next rhead;rhead cur;cur next;}return rhead;
}
思路(一) 创建新链表从前向后取出原链表的节点进行头插。 1. 开始时定义两个指针 cur 和 rhead。 cur 指向原始链表的头部 headrhead 用来构建反转后的链表初始为空表示反转后链表的尾部。 2. 进入循环这个循环将遍历整个链表并进行反转操作。循环的条件是 cur 不为 NULL表示还有节点需要处理。 3. 在循环内部首先创建一个临时指针 next 来保存 cur 的下一个节点因为在修改 cur-next 指针之前需要先保存下一个节点的信息否则会丢失对它的引用。 4. 接着将 cur-next 指向 rhead这一步实际上是将 cur 的下一个节点指向反转后链表的头部从而将 cur 从原链表中分离出来。 5. 更新 rhead 为 cur这一步将 cur 成为反转后链表的新头部。 6. 更新 cur 为 next这一步将 cur 移动到原链表中的下一个节点准备处理下一个节点。 7. 循环继续执行直到 cur 变为 NULL表示已经遍历完整个链表。此时rhead 指向反转后链表的头部。 8. 返回 rhead它现在指向反转后的链表的头部完成链表的反转。 struct ListNode* reverseList(struct ListNode* head) {if (head NULL)return NULL;struct ListNode* n1 NULL;struct ListNode* n2 head;struct ListNode* n3 n2-next;while (n2) {n2-next n1;n1 n2;n2 n3;if (n3)n3 n3-next;}return n1;
} 思路(二)调转链表方向三指针
n1 初始化为 NULL表示反转后的链表的尾部。n2 初始化为链表的头部节点 head。n3 初始化为 n2 的下一个节点即 n2-next。 1、进入循环这个循环将遍历整个链表并反转节点。 2、在循环内部首先将 n2 的 next 指针指向 n1这是为了将 n2 的指针方向反转将其指向前一个节点 n1而不是原来的下一个节点。 3、接着更新 n1 和 n2将它们分别向前移动一个节点。n1 移动到 n2 的位置n2 移动到 n3 的位置。 4、继续检查 n3 是否为 NULL。如果 n3 不为 NULL将 n3 移动到它的下一个节点以便在下一轮循环中使用。 5、循环继续执行直到 n2 为 NULL表示已经遍历完整个链表。此时n1 指向原链表的最后一个节点它成为了反转后链表的头部。 6、返回 n1它现在指向反转后的链表的头部完成了链表的反转。 五、求链表中倒数第k个结点
链表中倒数第k个结点_牛客题霸_牛客网 (nowcoder.com) 输入一个链表输出该链表中倒数第k个结点。 struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {struct ListNode* slowpListHead,*fastpListHead;int n0;while(k){if(fastNULL)return 0;fastfast-next;k--;}while(fast){slowslow-next;fastfast-next;}return slow;
}
思路 快慢指针
快慢指针的速度都为1步快指针先走k步然后慢指针开始与快指针同时走快指针走到最后为空时慢指针则为倒数第k个节点。 1、通过while循环先让fast走k步如果fast为空则无法求出倒数第k个节点k大于链表长度返回值为0。 2、第二个while循环slow和fast开始同时向后走fast为空时slow指向的节点即为所求倒数第k个节点。 六、链表分割
链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 现有一链表的头指针 ListNode* pHead给一定值x编写一段代码将所有小于x的结点排在其余结点之前且不能改变原来的数据顺序返回重新排列后的链表的头指针。 class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;lesshead lesstail (struct ListNode*)malloc(sizeof(struct ListNode));greaterhead greatertail (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur pHead;while (cur) {if (cur-val x) {lesstail-next cur;lesstail lesstail-next;}else {greatertail-next cur;greatertail greatertail-next;}cur cur-next;}lesstail-next greaterhead-next;greatertail-next NULL;pHead lesshead-next;free(lesshead);free(greaterhead);return pHead;}
}; 思路假设x5链表各节点值为如下图 1、创建变量* lesshead, * lesstail为小于x的链表的头节点和尾节点, * greaterhead, * greatertail 为大于x的链表的头节点和尾节点。 为两个新链表头节点开辟空间储存值val和指向下一个节点next。 2、在循环中判断cur的值是否小于x小于则将cur链接到less链表不小于则链接到grearter链表。 3、两个新链表需要链接合并成完整链表。 4、greatertail-next NULL 这一步一定不能少否则可以会出现循环链表 七、链表的回文结构
链表的回文结构_牛客题霸_牛客网 (nowcoder.com) 对于一个链表请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法判断其是否为回文结构。 给定一个链表的头指针A请返回一个bool值代表其是否为回文结构。保证链表长度小于等于900。 测试样例 1-2-2-1 返回trueclass PalindromeList {
public:struct ListNode* middleNode(struct ListNode* head){struct ListNode* slowhead;struct ListNode* fasthead;while(fastfast-next){fastfast-next-next;slowslow-next;}return slow;}struct ListNode* reverseList(struct ListNode* head){struct ListNode* curhead,*rheadNULL;while(cur){struct ListNode* nextcur-next;cur-nextrhead;rheadcur;curnext;}return rhead;}bool chkPalindrome(ListNode* head) {struct ListNode* midmiddleNode(head);struct ListNode* rmidreverseList(mid);while(rmid){if(rmid-valhead-val){rmidrmid-next;headhead-next;}else{return false;}}return true;}
};
思路从中间点开始逆置
八、判断链表是否相交
160. 相交链表 给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的节点。如果两个链表不存在相交节点返回 null 。 图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。注意函数返回结果后链表必须 保持其原始结构 。 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode * tailAheadA;struct ListNode * tailBheadB;int lenA1,lenB1;while(tailA-next){tailAtailA-next;lenA;}while(tailB-next){tailBtailB-next;lenB;}if(tailA!tailB){return NULL;}int gapabs(lenA-lenB);struct ListNode * longListheadA;struct ListNode * shortListheadB;if(lenAlenB){longListheadB;shortListheadA;}while(gap--){longListlongList-next;}while(longList!shortList){longListlongList-next;shortListshortList-next;}return longList;
} 思路长的链表走相差长度步数然后短的开始和长的同时走节点地址相等则相交。 1、定义变量 tailA 和 tailB 分别指向链表A和B的头节点分别遍历对应链表获得链表长度lenA和lenB因为while循环结束条件是tail-next为空所以len的值初始化为1。 2、通过比较 tailA 和 tailB 是否相等来判断两个链表的尾节点是否一致。如果不相等说明两个链表不可能有公共节点直接返回 NULL。 3、使用abs函数求出链表A与B长度差值差值赋值给变量gap。 4、 创建两个指针longlist和shortlist分别指向链表A和B的头节点然后判断链表大小如果lenA大于lenB则 longListheadB否则 shortListheadA。 5、 longlist先向后走gap步为了保持和shortlist同步遍历。 6、longlist和shortlist同时向后遍历当二者相等时停止遍历返回二者任意一个即为两个单链表相交的起始节点。 九、判断链表中是否有环(一)
141. 环形链表 给你一个链表的头节点 head 判断链表中是否有环。 注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 示例 1 输入head [3,2,0,-4], pos 1输出true解释链表中有一个环其尾部连接到第二个节点。 bool hasCycle(struct ListNode *head) {struct ListNode *fasthead;struct ListNode *slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow)return true;}return false;
} 思路快慢指针
指针slow一次走一步指针fast一次走两步这样在链表中走如果有环存在则二者一定会相遇因为fast是slow速度的两倍。如果fast走到最后为空证明该链表没有环存在。 当fast步数 十、 判断链表中是否有环(二)
142. 环形链表 II 给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。 不允许修改 链表。 示例 1 输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。 struct ListNode* detectCycle(struct ListNode* head) {struct ListNode* fast head;struct ListNode* slow head;while (fast fast-next) {slow slow-next;fast fast-next-next;if (fast slow) {struct ListNode* meet slow;while (head ! meet) {head head-next;meet meet-next;}return meet;}}return NULL;
} 思路快慢指针 slow一次走一步fast一次走两步他们都从头节点head位置开始移动。 设head到入环节点的距离为L假设第一次相遇位置为meet入环节点到meet的距离为X相遇位置到入环节点的距离为环的周长C减去X。 slow走的路程LX fast走的路程 LXn*Cslow进环前fast走了n圈比如环很小则fast可能走了好几圈slow才进环。 因为fast的速度是slow的两倍所以fast走的路程是slow的两倍一圈之内fast一定追上slow 由此可以得到以下关系式2(LX)LXn*C 化简得到Ln*C-X 即 L(n-1)CC-X 这样就知道了 LC-X即一个指针从相遇点开始走一个指针从头节点开始走他们会在入环点相遇。
