地产网站开发公司,旅游网页设计模板简约图片,环境设计专业作品集,福建省城乡建设厅网站文章目录前言移除链表元素相交链表写在最后前言 本章的OJ练习也是相对简单的#xff0c;只要能够理解解题的思路#xff0c;并且依照这个思路能够快速的写出代码#xff0c;我相信#xff0c;你的链表水平已经足够了。 对于OJ练习#xff08;2#xff09; : -传送门…
文章目录前言移除链表元素相交链表写在最后前言 本章的OJ练习也是相对简单的只要能够理解解题的思路并且依照这个思路能够快速的写出代码我相信你的链表水平已经足够了。 对于OJ练习2 : -传送门-。其中两道题都可运用快慢指针的解题思路这使得两个题都只需要遍历一次链表即可解答。 对于本章是链表的OJ练习的最后一篇较为简单的章节后续的OJ练习将会上难度。 移除链表元素 题目链接- 传送门 -。 该题目的描述为给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 这里我们采用的方法是在原链表的基础上重新连接节点将 Node.val val 的节点跳过不连接。 我们重新定义一个指向新连接的链表的头节点的指针newhead,然后在定义一个用来连接的指针cur,最终连接好后返回newhead即可。 将 Node.val val 的节点作为新连接的链表的结点 如果一开始head为空或者head链表里全是等于val的结点初始化newnode cur NULL此时连接操作就不进行后面返回newnode一直为NULL即可。 下面是代码实现
struct ListNode* removeElements(struct ListNode* head, int val){// cur为对新连接的链表的连接指针newhead为新连接的链表的指向头节点的指针struct ListNode* cur NULL, * newhead NULL;struct ListNode* tmp head;while (tmp){if (tmp-val ! val) // 如果不等于val就连接{if (newhead NULL) // 连接时如果新的头为空就将该节点作为头节点{newhead cur tmp;}else // 正常连接{cur-next tmp;cur cur-next;}}tmp tmp-next; // 到下一个节点判断}// 如果head为空或者head链表里面所有节点的val都为所给的val就说明没有新的头这里判断是为了防止空指针解引用// 如果是正常情况需要将新连接的最后一个节点的next指向NULL如果已经指向NULL多操作一步也没有问题if (cur) cur-next NULL;// 最后返回新连接的链表的头return newhead;
}相交链表 题目链接- 传送门 -。 该题目描述为给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。
也就是 解题思路【双指针遍历】 首先我们可以先判断这两个链表是否有一个为空或者都为空有空的情况那么一定不相交此时直接返回NULL。 如果两个链表相交那么从相交的那个起始节点开始后面的长度是相同的。由此我们定义两个指针pa与pb分别指向headA的头节点与headB的头节点并同时向后遍历链表。 如果pa不为NULL则移到下一个节点如果pb不为空也移到下一个节点。如果第一次遍历pa为空则将pa指向headB的头节点如果第一次遍历pb为空则将pb指向headA的头节点。至于到底相不相交第二遍遍历会见分晓。 我们假设两个链表相交那么设从相交的初始节点开始到NULL的长度为nheadA的头节点到相交的初始节点的长度为xheadB的头节点到相交的初始节点的长度为y。按照上一条的思路当pa第一次遍历到达NULL时pa一共走了x n的长度此时将pa指向headB的头节点当pb第一次遍历到达NULL时pb一共走了y n的长度此时将pb指向headA的头节点。仔细思考就会发现pa在headB走到相交的初始节点还需走y的长度此时pa一共走了x n ypb在headA走到相交的初始节点还需走x的长度此时pb一共走了y n x。这时pa走的长度与pb走的长度恰好相等且pa与pb都刚好指向相交的初始节点。所以该方法能够有效的找出那个相交的初始节点。 如果两个链表不相交也是一样通过双指针分别依次向后遍历链表。如果两个链表长度相等最终pa与pb在第一次遍历的时候就都会到达NULL此时返回NULL如果两个链表长度不相等同样的在第一次遍历时只要pa或者pb指向NULL就将pa或者pb指向另外一个链表的头节点然后继续遍历。我们假设headA链表的长度为xheadB链表的长度为y当pa第一次遍历指向NULL时走的长度为x此时将pa指向headB的头节点当pb第一次遍历指向NULL时走的长度为y此时将pb指向headA的头节点。不出所料两个指针在第二次遍历链表时最后同时指向NULL这是因为pa在headB的遍历要走的长度为y此时pa总共走的长度为x ypb在headA的遍历要走的长度为x此时pb总共走的长度为y x。可以看到第二次遍历走完两个指针走的长度是相同的并且两个指针都是指向NULL。所以两个链表不相交遍历的两个指针最终都是同时指向NULL。 下面是代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {// 如果其中有一个链表为空或者全为空说明不可能相交直接返回NULLif(headA NULL || headB NULL) return NULL;struct ListNode* pa headA, * pb headB;// 对于headA与headB只有相交与不相交的情况// 相交则跳出循环// 不相交则再循环里面就返回// pa pb说明找到相交的初始节点了条件判断为假跳出循环while (pa ! pb){// 同步向后遍历pa pa-next;pb pb-next;// 如果两个指针都指向空说明headA与headB不相交if (pa NULL pb NULL) return NULL;// 如果pa遍历完headA就到headB继续遍历if (pa NULL) pa headB;// 如果pb遍历完headB就到headA继续遍历if (pb NULL) pb headA;} // 这里返回pa或者pb都是可以的都指向相交的那个初始节点return pa;
}写在最后 对于单链表的题目练习最重要的是思路我们在数据结构阶段要养成画图的习惯因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。 感谢阅读本小白的博客错误的地方请严厉指出噢
