数据结构习题-- 相交链表

数据结构习题-- 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null

如上图，返回c1结点
注意：这两个链表非环形

方法：集合

分析

由题找到两个链表最先相交的部分，我们可以先遍历一个链表，然后将其每个节点存入集合，然后再遍历另一个链表，每次遍历并判断，该元素是否在集合当中

代码

public class intersectedList {
// 定义结点
    class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            HashSet<ListNode> hashSet = new HashSet<>();
            // 遍历链表A并把其每个节点存储在集合当中
            ListNode tempA = headA;
            while (tempA != null){
                hashSet.add(tempA);
                tempA = tempA.next;
            }
            // 遍历链表B，每一个节点判断是否在集合当中，如果在就返回该结点
            ListNode tempB  = headB;
            while (tempB != null){
                if (hashSet.contains(tempB)){
                    return tempB;
                }
                tempB = tempB.next;
            }
            return null;
        }
    }
}

方法：双指针(推荐)

分析

首先我们知道，一但两条链表相交，那么相交部分后都是相同的
那么如果我们从后面往前看每个结点都是相同的，找到第一个相同的点，就是题目中的点
如： 123654
xxxxxxx2654
两条字符串，x表示占位，我们发现从后面往前看，654是公共的部分，而对于一长一短两条链表，公共部分的最大长度最多只能是短的那条链表，我们只需要从短链表开始的位置，和长链表对应的位置一一比较就行，在上述例子中，我们就应该从长链表的3开始，而短链表从2开始，这样如果相同的话，其后面部分长度是相同的

而长链表的1，2绝对不可能是公共的交点，但是在实际处理中，我们不可能不遍历就知道链表长度，所以通过 把一条链表 A 和另外一条链表 B拼接，就能实现对齐，一条拼接为 A + B ，另一条为 B + A，这样就可以实现长度相同
A + B：123654 / 2654
B + A：2654 / 123654
其中的 / 表示把A,B分隔开的一个标识
A + B：123654 / 2654
B + A：2654 / 123654
如上，在非加粗的部分是不可能有相同点的，还是那个原因，因为如果是交点，其后面应该完全一样，但是其后面长度不相同，而到加粗部分就是真正的比较部分

代码

package LinkList;

public class intersectedListPlus {
    class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode aBegin = headA;
            ListNode bBegin = headB;
            // 因为最多只变轨两次，设置变量控制变轨次数
            int changeNum = 0;
            // 因为一个是 A + B,一个是 B + A
            // 最后它们达到的结尾是相同的，所以当它们到最后肯定是一起为 null
            // 而因为A B链表的长度可能不同所以不能把循环条件设置为 其中一个为null
            while (aBegin != null && bBegin != null){
                // 判断两个结点是否相同，相同就返回
                if (aBegin == bBegin){
                    return aBegin;
                }
                // 更新结点
                aBegin = aBegin.next;
                bBegin = bBegin.next;
                // 如果变轨次数小于2，且此时aBegin达到 null时，将其设置 到headB，完成变轨拼接
                if (aBegin == null && changeNum < 2){
                    aBegin = headB;
                    changeNum++;
                }
                // 如果变轨次数小于2，且此时bBegin达到 null时，将其设置 到headA，完成变轨拼接
                if (bBegin == null && changeNum < 2){
                    bBegin = headA;
                    changeNum++;
                }
            }
            return null;
        }