160. Intersection of Two Linked

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8

题目要求

判断两个链表是否有交点，有则返回交点，无则返回空

思路

两个指针分别遍历listA和listB，当两个指针所指节点一样时，则有交点，否则无交点。
但现在问题是两个链表长度未知，所以两个指针起始位置偏差也未知，这样就无法同时遍历到交点。所以可以先求链表长度差k，将长的链表指针先走n步，则两指针来到同一起跑线，再一起走，判断是否相同，就可以找到节点了。

代码

 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         int la=0,lb=0;//记录表长度
         ListNode headaa =headA;
         ListNode headbb =headB;
         
         while (headaa!=null) {
             la++;
            headaa=headaa.next;
        }
         while (headbb!=null) {
             lb++;
            headbb=headbb.next;
        }
         
         headaa =headA;
         headbb =headB;
         int k =la-lb;
         
         if (k>0) {//长的先走k步
            while (k>0) {
                headaa=headaa.next;
                k--;
            }
        }else if (k<0) {
            while (k<0) {
                headbb=headbb.next;
                k++;
            }
        }
         
         while (headaa!=null&&headbb!=null) {//再一起走，相同则返回当前节点
            if (headaa==headbb) {
                return headaa;
            }
            headaa=headaa.next;
            headbb=headbb.next;
        }
         
         
         
        return null;//没有则返回空
            
        }