leecode 解题总结：160. Intersection of Two Linked Lists

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题:Write a PRogram to find the node at which the intersection of two singly linked lists begins.For example, the following two linked lists:A:          a1 → a2                   ↘                     c1 → c2 → c3                   ↗            B:     b1 → b2 → b3begin to intersect at node c1.Notes:If the two linked lists have no intersection at all, return null.The linked lists must retain their original structure after the function returns.You may assume there are no cycles anywhere in the entire linked structure.Your code should preferably run in O(n) time and use only O(1) memory.Credits:Special thanks to @stellari for adding this problem and creating all test cases.分析:写一个程序，判断两个链表交叉处的第一个结点，如果没有交叉，返回NULL。不能改变原有结构必须在O(n)时间内完成，使用O(1)的空间。这个是数据结构上的。因为两个链表如果交叉的话，肯定是最后一段交叉了。可以遍历两个链表，得到长度L1,L2,设较长的长度为lMax,较短的长度为lMin，然后让较长的链表先走lMax - lMin步，然后一起走，此时判断两个指针是否相等，如果相等后面必定交叉返回当前指针；如果走到最后，指针为空了，返回NULL关键:1 要细心报错:Input:Intersected at '1': [1][1]Output:No intersectionExpected:Intersected at '1'是因为我忘记将遍历的指针重新设置为原始值		nodeA = headA;		nodeB = headB;		//链表A比较长,A链表先走steps步		if(lA > lB)		{			for(int i = 0 ; i < step ; i++)			{				nodeA = nodeA->next;			}		}*/struct ListNode {	 int val;	 ListNode *next;    ListNode(int x) : val(x), next(NULL) {}};class Solution {public:    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {		if(NULL == headA || NULL == headB)		{			return NULL;		}        int lA = 0;		ListNode* nodeA = headA;		while(nodeA)		{			lA++;			nodeA = nodeA->next;		}		int lB = 0;		ListNode* nodeB = headB;		while(nodeB)		{			lB++;			nodeB = nodeB->next;		}		int step = max(lA , lB) - min(lA, lB);		nodeA = headA;		nodeB = headB;		//链表A比较长,A链表先走steps步		if(lA > lB)		{			for(int i = 0 ; i < step ; i++)			{				nodeA = nodeA->next;			}		}		else		{			for(int i = 0 ; i < step ; i++)			{				nodeB = nodeB->next;			}		}		//两个链表一起走		while(nodeA && nodeB)		{			if(nodeA == nodeB)			{				return nodeA;			}			nodeA = nodeA->next;			nodeB = nodeB->next;		}		return NULL;    }};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}