两个链表的第一个公共节点

た入场券 2022-12-04 08:54 149阅读 0赞

# 两个链表的第一个公共节点 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/

https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/shuang-zhi-zhen-fa-lang-man-xiang-yu-by-ml-zimingm/

## 2、题目要求 ##

> **题目描述**

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表，在 `c1` 节点开始相交

![image-20200906223217077][]

> **注意：**

1.  如果两个链表没有交点，返回 `null`
2.  在返回结果后，两个链表仍须保持原有的结构。
3.  可假定整个链表结构中没有循环。
4.  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

## 3、代码思路 ##

使用 `HashSet`

1.  先遍历第一个链表，将其所有节点都添加到 `HashSet` 中，再遍历第二个链表，利用 `set.contains()` 判断第二个链表中的节点是否与第一个链表中的节点为同一个节点
2.  这样做是可行的，因为我们没有重写 `ListNode` 的 `hahsCode()` 方法，在 `set` 中我们存储的是链表节点的内存地址

--------------------

使用双指针

1.  假如两个链表长度相同，使用双指针挨个判断肯定没有问题，但问题就在于两个链表长度不一致，这怎么办？
2.  双指针又来了，这样来想，两个人在不同长度的直线跑道上跑步，两个人的速度相同，当跑到尽头时，便重新回到起点，继续开始跑步，这两个人肯定会相遇
3.  下面的代码便运用了这样的思路，分别为两个链表定义一个指针：`list1Pointer` 和 `list2Pointer`，`list1Pointer` 和 `list2Pointer` 以每次一步的速度往后移动，当走到尽头时(`null`)，便回到起点(`head`)，这样 `list1Pointer` 和 `list2Pointer` 总会相等

![image-20200907140832015][]

## 4、代码实现 ##

使用 `HashSet`：

public class Solution {
        
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
    
            ListNode list1Pointer = headA;
            ListNode list2Pointer = headB;
            HashSet<ListNode> set = new HashSet<>();
    
    
            while (list1Pointer != null) {
        
                set.add(list1Pointer);
                list1Pointer = list1Pointer.next;
            }
    
            while (list2Pointer != null) {
        
                if(set.contains(list2Pointer)){
        
                    return list2Pointer;
                }
                list2Pointer = list2Pointer.next;
            }
    
            return null;
        }
    }
    
    public class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
            next = null;
        }
    }

使用双指针

public class Solution {
        
    
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
            ListNode list1Pointer = headA;
            ListNode list2Pointer = headB;
            while (list1Pointer != list2Pointer) {
        
                // 如果到达尾部，则返回值首节点
                if(list1Pointer != null){
        
                    list1Pointer = list1Pointer.next;
                }else{
        
                    list1Pointer = headA;
                }
                // 如果到达尾部，则返回值首节点
                if(list2Pointer!=null){
        
                    list2Pointer = list2Pointer.next;
                }else{
        
                    list2Pointer = headB;
                }
            }
            return list1Pointer;
        }
    
    }
    
    public class ListNode {
        
        int val;
        ListNode next;
    
        ListNode(int x) {
        
            val = x;
            next = null;
        }
    }

[image-20200906223217077]: /images/20221123/613233f33d6146858e4e05571fe60fec.png
[image-20200907140832015]: /images/20221123/d68ae95f918a41c786273d4cff75b7c1.png