Java for 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.

解题思路：

先遍历两个list的长度，然后长的减去短的，之后同时遍历即可，JAVA实现如下：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if(headA==null||headB==null)

        	return null;

        int lengthA=0,lengthB=0;

        ListNode tempA=headA,tempB=headB;

    	while(tempA!=null){

    		tempA=tempA.next;

    		lengthA++;

        }

    	while(tempB!=null){

    		tempB=tempB.next;

    		lengthB++;

        }

    	if(lengthB>lengthA){

    		tempA=headA;

    		headA=headB;

    		headB=tempA;

    		int temp=lengthA;

    		lengthA=lengthB;

    		lengthB=temp;

    	}

    	int length=lengthA-lengthB;

    	while(length-->0)

    		headA=headA.next;

    	while(headA!=null){

    		if(headA==headB)

    			return headA;

    		headA=headA.next;

    		headB=headB.next;

    	}

    	return headA;

    }

巴特西

Java for LeetCode 160 Intersection of Two Linked Lists

最新文章

热门文章