首页 > 代码库 > 【Leetcode】Intersection of Two Linked Lists in JAVA

【Leetcode】Intersection of Two Linked Lists in JAVA

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.

还是倒着想,把listnode放进栈里,然后一个一个pop出来,直到不一样的话,那么前一个点为合并点。

网上都没查到还有别的写这道题的,看来我是第一波写这个题的了~

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
		
		if(headA==null||headB==null)	return null;
        Stack<ListNode>	stackA = new Stack<ListNode>();
        Stack<ListNode>	stackB = new Stack<ListNode>();
	Stack<ListNode>	stackC = new Stack<ListNode>();//为了最后输出的合并listnode
        ListNode a = headA;
        ListNode b = headB;
        int i=1,j=1;
		while(a.next!=null)	{
			stackA.push(a);
			a=a.next;
			i++;
		}
		stackA.push(a);//到此为止,把所有的listnode push进stackA,如是下面stackB
		while(b.next!=null){
			stackB.push(b);
			b=b.next;
			j++;
		}
		stackB.push(b);//同上
		if(a.val!=b.val)	return null;
		
		while(i>0&&j>0){
			ListNode bottomA=stackA.pop();
			ListNode bottomB=stackB.pop();
			if(bottomB.val==bottomA.val)	//如果a和b的stack pop出来一样,存进C里,不一样的话那就输出
				{
				stackC.push(bottomA);
				i--;
				j--;
				}
			else	{
				return stackC.pop();
			}
		}
		if(i==0)	return headA;//如果某一个已经到头了,那么就是head为合并点
		else return headB;
    }


【Leetcode】Intersection of Two Linked Lists in JAVA