口碑好的秦皇岛网站建设哪家好广州网页制作

链表相交

题目链接

解题思路：

1. 题目可以确定如果相交，那么相交的部分一定是在链表的结尾部分
2. 第一步求得两条链表的长度
3. 第二步长度做差，将长的那条链表与短的那条链表后部分对其
4. 第三步遍历后面的部分，如果当前节点相等，直接返回，否则返回null

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {int lenA=0;int lenB=0;ListNode* curA = headA;ListNode* curB = headB;while (curA != NULL) {lenA++;curA = curA->next;}while (curB != NULL) {lenB++;curB = curB->next;}curA = headA;curB = headB;if (lenA > lenB) {int temp = lenA - lenB;while (temp--) {curA = curA->next;}while (curA != NULL) {if (curA == curB) {return curA;}curA = curA->next;curB = curB->next;}}else{int temp = lenB - lenA;while (temp--) {curB = curB->next;}while (curB != NULL) {if (curA == curB) {return curA;}curA = curA->next;curB = curB->next;}}return NULL;}
};