摘要

剑指offer面试题 37  ： 给两个单链表链表 ，，，找出他们的第一个相遇节点 链表节点的定义如下： //链表节点的定义 struct ListNode { int _data; ListNode* _next; };

实现方法

看到这道题的第一感觉就是死方法，，，；；； 在第一个链表的   逐步遍历链表节点，，，， 每遍历一个节点的时候   ，，，，同时顺序遍历链表2 的每一各节点 此种做法的时间复杂度就是有点大了   O（M+N） 代码的实现 //方法1 死方法 直接遍历两个链表 ，，，，这样的做法的时间复杂度为O（M*N） ListNode* GetMeetNode1(ListNode* head1,ListNode* head2) { ListNode * cur1 =head1; while(cur1)//遍历链表1 { ListNode* cur2 = head2;//顺序遍历链表2 while(cur2) { if(cur1 == cur2)//要是两个节点相同，，表示就是第一个相遇节点 { return cur1; } cur2 =cur2->_next; } cur1= cur1->_next; } return NULL;//表示的是两个链表没有相遇节点 } 上面的做法只是一般人    的做法；；； 你要是觉得你不是一般人的话 ，，，，就往下来看    上面的代码的时间复杂度有点大了  。。。。。 但是我们要怎么来减少时间复杂度呢  ？？？？？？？？？？？ 我们都知道   两个链表的相交一般就是两种情况  ：：： Y型相交； V型相交。。。。 这两种相交的情形都有一个共同点 ；；；； 他们的尾节点都是一样的。。。。 所以我们可以从尾部向前来判断，，，，找到最后的一个相同的节点  就是   所谓的第一个相遇节点。。。。 但是要  ，，实现这种的操作的；；我们就必须先找到最后一个节点 ，，，，并把前面的节点保存起来。。。。 这个有点像是     "后进先出"的原则。。。。。 所以我们想到了用栈来实现  。。。。。这也就是所谓的以空间来换取时间的做法 这样的时间复杂度就是O（M+N）  空间复杂度为O（M+N）；；； 代码的实现 //方法2： 两个链表的相交有两种的方式 //1、Y型相交 //2、V型相交 //我们可以看到这两种情况 都有一个共同点：他们两个的尾节点重合 //我们只要从后往前两遍历 最后一个相同的节点就是他们的相遇节点 //时间复杂度的最坏的情况为O（M+N+N） //但是空间复杂度有点大 #include<stack> ListNode* GetMeetNode2(ListNode* head1,ListNode* head2) { ListNode * cur1 = head1; ListNode * cur2 = head2; //若要从后往前来判断 ，，，就是一种后进先出的想法；；；使用栈 stack<ListNode*> s1;//用来保存两个链表的值 stack<ListNode*> s2; while(cur1)//存储链表1 { s1.push(cur1); cur1= cur1 ->_next; } while(cur2)//存储链表2 { s2.push(cur2); cur2= cur2 ->_next; } cur1 = s1.top(); cur2 = s2.top(); s1.pop(); s2.pop(); if(cur1 != cur2)//表示的是 他们没有相遇节点 return NULL;//表示的是两个链表没有相遇节点 while(cur1 == cur2) { if(!s1.empty() || !s2.empty())//表示的是 链表1结束或者链表2结束 return cur1; cur1 = s1.top(); cur2 = s2.top(); s1.pop(); s2.pop(); } //走到这里cur1 表示的是最后一个不想同的节点 return cur1->_next; } 要是你可以做到这一步的话 ，，那就是也能说明：：： 你只是比普通人要好一点 ，，， 但是要是面试的话，，，，面试官肯定还是不满意 。。。。 既然，，，你都能把时间复杂度降下来，，，，，为什么不能把空间复杂度也降下来呢？？？ 一般的链表的相交的问题就是这个样子的，，图中    我们可以清楚的看到的如果两个链表同分别从      3     和      5 开始向后判断   ，，， 当两个节点相同的时候 ，，，得到的就是第一个相遇节点  但是，，，要是实现这种    解法，，，我们就要    知道怎么得到     3  和  5这两个节点  我们可以来得到两个链表的长度 ，，，先将 让长的链表先走（m-n）部 //方法三：上面的两种情况 不是时间复杂度太高，，就是空间复杂度太大 //所以我们想出了第三种情况 //先得到两个链表的长度 int GetListSize(ListNode* head) { int count = 0 ; while(head) { head = head->_next; count++; } return count; } ListNode* GetMeetNode3(ListNode* head1,ListNode* head2) { //先得到两个链表的长度 int size1 = GetListSize(head1); int size2 = GetListSize(head2); ListNode* longNode = head1;//定义一个长的链表节点 ListNode* shortNode = head2;//定义一个短的链表节点 int n = size1- size2; if(size1 < size2)//做的适量的调整 { n = size2 -size1; longNode =head2; shortNode =head1; } for(int i = 0 ;i < n;++i) { longNode = longNode ->_next; } while(shortNode && longNode &&shortNode!= longNode) { shortNode = shortNode->_next; longNode = longNode->_next; } return shortNode; }