链表相交 三种思路 C++ 代码
2021/5/15 14:25:10
本文主要是介绍链表相交 三种思路 C++ 代码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
方法1 回环法 讲listA & listB看成一个环
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { //回环法 讲listA & listB看成一个环 //e.g listA = [9,1,8,4,5] listB = [1,8,4,5] // posA=4 ,posB =5 // goon posA=5 posB=9 // goon posA= 1 ,posB=1 ,ok finish ListNode * posA= headA,*posB = headB; bool AExchangeFlag=false; if(!headB || !headA ) return NULL; while(!AExchangeFlag || posA ) { if(posA == posB ) return posA; posA= posA->next; posB = posB->next; //在A没有执行交换情况下 if(!AExchangeFlag && posA== NULL ) { AExchangeFlag=true; posA= headB; } if(posB==NULL ) posB = headA; } return NULL; } };
方法2 stack 法,从后往前找到第一个不等的地方
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { //stack 法,找到第一个不等的地方 //e.g listA = [9,1,8,4,5] listB = [1,8,4,5] // stackA =9 != listB=NULL, return --listA std::stack<ListNode*> stackA, stackB; while(headA) { stackA.push(headA); headA= headA->next; } while(headB) { stackB.push(headB); headB = headB->next; } if(stackA.size()< stackB.size() ) std::swap(stackA,stackB); ListNode * preA= NULL; while(!stackB.empty()) { auto tA= stackA.top(); stackA.pop(); auto tB= stackB.top(); stackB.pop(); if(tA!= tB) return preA; preA = tA; } return preA; } };
方法3 对齐法 先计算出长度差
class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { // 对齐法 先计算出长度差 // listA = [9,1,8,4,5] listB = [7,8,4,5] // posA= 1 ,posB=7 // posA=8 ,pos=8 ok auto posA= headA, posB= headB; //to get lenA ,lenB int lenA=0,lenB=0; while(posA) { lenA++; posA= posA->next; } while(posB) { lenB++; posB= posB->next; } if(lenA < lenB ) { std::swap(headA,headB); std::swap(lenA,lenB); } int difLen= lenA-lenB; posA = headA; while(difLen) { posA= posA->next; difLen--; } //now same len posB= headB; while(posA) { if(posA == posB) return posA; posA= posA -> next; posB= posB -> next; } return NULL; } };
这篇关于链表相交 三种思路 C++ 代码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解