找两个链表第一次指针相同的地方

 

 

想法：（本来是没有的，因为没读懂题目描述= =）

1.两个指针，长的先走（长减短相差的长度）这么多的步数，然后就可以开始比较指针，直到指向为空，期间如果指针相同，返回该节点，如果链表未相交，则返回的是null

 

可是这是链表啊！没法知道长度！！！

 

 

2.hashset

将长链表的元素放入set，从短链表的头部开始，依次向后判断该元素是否在set中，如果是则表明两个链表相交，返回该点，若到最后都没有，则两个链表不相交，返回null

 1 /**

 2 * Definition for singly-linked list.

 3 * public class ListNode {

 4 *     int val;

 5 *     ListNode next;

 6 *     ListNode(int x) {

 7 *         val = x;

 8 *         next = null;

 9 *     }

10 * }

11 */

12 public class Solution {

13     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

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

15             return null;

16         }

17         Set setList = new HashSet<>();

18         while(headA!=null){

19             setList.add(headA);

20             headA = headA.next;

21         }//将一链表的元素放入set

22         while(headB!=null){

23             if(setList.contains(headB)){

24                 return headB;

25             }

26             headB = headB.next;

27         }//从另一链表的头部开始，依次向后判断该元素是否在set中，如果是则表明两个链表相交，返回该点，若到最后都没有，则两个链表不相交，返回null

28         return null;

29     }

30 }

 

如果像左边情况一样，两链表相加，长链表长度6，短链表长度4，相交长度2。甲从长链表头开始走，乙从短链表头开始走，甲乙走到空时从另一个链表的头开始走，甲走了4+2+2=乙走了2+2+4，之后甲乙相遇，返回该点，如果向右边情况一样，两个长度不等且不相交的链表，甲走6+3=乙走3+6，之后甲乙相遇，在null，返回null。

 

 

该方法就是：

【

当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

 

每步操作需要同时更新指针 pA 和 pB

如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点

如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点

当指针 pA 和 pB 相遇时返回该节点。都为空时，返回 null

 

作者：dodo_1202

链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/c-jiao-cha-bian-li-shuang-zhi-zhen-by-do-6eb1/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

】

 

 

使用for进行一个经过一次指针为空的循环（n<3）{

    判断pa pb是否相遇，若相遇返回该点，若不相遇继续下面：

    pa pb向前移动

    if（pa此时为空），则pa移到headb重新开始，中间变量 n+1；

    if（pb此时为空），则pb移到heada重新开始，中间变量 n+1；

}

到了这里说明双链表不相交

返回null