两个链表中的第一个公共节点（java）

题目描述：

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

分析：

思路一：暴力解法，强烈不建议！
遍历第一个链表的每个节点，同时每次都遍历一遍另一个链表，看是否有节点和这个节点相同，如果有相同节点就是公共节点，如果没有，就继续向下遍历。

---

思路二：长链表先走，再同步遍历
两个链表比较长短，计算出两者的长度差x，比较长的链表先往前走x步，然后长短链表一起同步向前走，看遍历到的节点是否相同，如果相同就是第一个公共节点。

---

思路三：用hashMap数据结构
第一个while循环遍历第一个链表，将其所有节点放入hashmap中
第二个while遍历第二个链表，用containsKey判断这个节点值是否存在第一个链表中。
（这种思路基本上就是用空间换时间）

---

思路四：两个链表的公共节点一定在链表的尾部
若连个链表存在公共节点，则它们的尾部一定从第一个公共节点开始完全相同。

我们分析有公共结点的两个链表有哪些特点。从链表结点的定义可以看出，这两个链表是单链表。如果两个单向链表有公共的结点，那么这两个链表从某一结点开始，它们的next都指向同一个结点，但由于是单向链表的结点，之后他们所有结点都是重合的，不可能再出现分叉。所以两个有公共结点而部分重合的链表，拓扑形状开起来像一个Y，而不可能像X。

两个链表的公共节点图解
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

解答：

思路二：长链表先走n步，然后长短链表共同向前遍历

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 if (pHead1 == null || pHead2 == null) return null;
        if (pHead1 == pHead2) return pHead1;
        int len1 = getLength(pHead1);
        int len2 = getLength(pHead2);
        //让比较长的链表先走几步
        if (len1 > len2) {
            for (int i = 0; i < (len1 - len2); i++) {
                pHead1 = pHead1.next;
            }
        } else {
            for (int i = 0; i < (len2 - len1); i++) {
                pHead2 = pHead2.next;
            }
        }
        boolean flag = false;  //标志位，判断是否走到第一个公共节点
        ListNode result = null;
        while (!flag) {
            if (pHead1 == null || pHead2 == null) {
                return null;
            }
            if (pHead1.val == pHead2.val) {
                flag = true;
                result = pHead1;
            } else {
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
        }
        return result;
    }

    /*求链表长度的方法，每次求链表涨肚，需要遍历一次单链表*/
    public static int getLength(ListNode pHead) {
        int len = 1;
        ListNode current = pHead;
        while (current.next != null) {
            len++;
            current = current.next;
        }
        return len;
    }
}

运行成功

这种方法可行，但是求链表的长度需要遍历一次链表，然后找到公共节点又要遍历两个链表，时间复杂度是O(M+N),但是鉴于每个链表都要遍历两遍，所以耗时还是比较多的。

如果想耗时比较少，可以考虑用空间换取时间，用hashmap存储链表1中的节点值，然后遍历一遍链表2即可。从hashmap中查找某个key值是否存在耗费的时间为O（1）。

---

思路四：当指针1访问到A的末尾开始访问B，当指针2访问到B的末尾开始访问A，这样，指针1,2会同时访问到公共节点。

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
   public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1, l2 = pHead2;
        while (l1 != l2) {
            l1 = (l1 == null) ? pHead2 : l1.next;
            l2 = (l2 == null) ? pHead1 : l2.next;
        }
        return l1;
    }
}

运行成功

简洁高效的代码是程序媛永恒的追求！