【LeetCode】160. Intersection of Two Linked Lists

问题描述

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 → b3

begin 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.

问题分析

首先求出两条链表的长度l1和l2，获取l1和l2的差值gap，然后让长的链表先走gap步，然后再两条链表同时走，如果中间有两个节点地址相同，即所求连接点。

代码

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==0||headB==0) return 0;
		
		ListNode* p = headA;
		ListNode* q = headB;
		
		int l1 = 0;
		int l2 = 0;
		
		while(p) {
			l1++;
			p=p->next;
		}
		while(q) {
			l2++;
			q=q->next;
		}
		int gap = l1 - l2;
		p = (gap>=0?headA:headB);
		q = (gap<0?headA:headB);
		gap = abs(gap);
		while(gap--) {
			p=p->next;
		}
		while(p!=0&&q!=0) {
			if(p==q) return p;
			p = p->next;
			q = q->next;	
		} 
	 	return 0;
    }
};