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

题目描述

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

公共节点定义：两个节点有相同的地址和value，缺一不可。

所以不能分别new两个节点node1,node2 ，否则

while(node1!=node2)始终为true, 循环退不出来。

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

链表定义：

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

    ListNode(int val) {
        this.val = val;
    }
}

分析：

所谓的公共节点，一定是两个链表共用的节点，不能new一个新的节点出来。

方法一、 第一反应就是采用蛮力的方法：在第一个链表上顺序遍历每个节点，每遍历到一个节点的时候，在第二个链表上顺序遍历每个节点。如果第二个链表上的节点和第一个链表上的节点一样，就说明两个链表在节点上重合，于是就找到了公共的节点。该算法的时间复杂的是 O(m*n)

方法二、从链表的定义可以看出，这两个链表是单链表，如果两个链表有公共节点，那么这两个链表从某一节点开始，它们的m_pNext都指向同一个节点，之后它们所有的节点都是重合的，不可能再出现分叉。所以拓扑形状看起来是Y型。如下图所示：

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

从链表头出发如何同时到达第一个相同的结点呢? 可以让其中长的链表先走几步，到达结合点后，两个链表剩余的部分就相同了。该算法的时间复杂度为：O(m+n)

 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1=pHead1;
        ListNode cur2=pHead2;
        if(pHead1==null||pHead2==null)
            return null;
        int len1=getLength(cur1);
        int len2=getLength(cur2);

//长的链表先多走几步
        if(len1>=len2){
            int len=len1-len2;
            while(len>0){
                cur1=cur1.next;
                len--;
            }
        }else{
            int len=len2-len1;
            while(len>0){
                cur2=cur2.next;
                len--;
            }
        }
        while(cur1!=cur2){//不一致的地方，一起往下走，直到一样
            cur1=cur1.next;
            cur2=cur2.next;
        }
        return cur1;

    }
    public static int getLength(ListNode phead){//计算链表长度
        int length=0;

        ListNode current =phead;
        while(current!=null){
            length++;
            current=current.next;
        }
        return length;
    }

方法三、用两个指针扫描”两个链表“，最终两个指针到达 null 或者到达公共结点。

分析，两个链表有公共节点，则有公共节点和节点后面的尾巴。

假设链表1的长度为a+c,链表2的长度为b+c. c为公共节点及后面的子节点部分，

假设a>c,则有链表长度 (a+c)+(b+c) = (b+c)+(a+c);

(a+c)+(b+c) 即链表1走完后跳转到链表2；

(b+c)+(a+c) 即链表2走完后跳转到链表1；

如图所示，如果有公共节点，则一定会在c处的节点相遇。

核心代码：

while(cur1!=cur2){
    cur1=(cur1==null? pHead2:cur1.next);//即链表1走完后跳转到链表2；
    cur2=(cur2==null? pHead1:cur2.next);//即链表2走完后跳转到链表1；
}

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

 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1=pHead1;
        ListNode cur2=pHead2;
        while(cur1!=cur2){
            cur1=(cur1==null? pHead2:cur1.next);
            cur2=(cur2==null? pHead1:cur2.next);
        }
        return cur1;
    }

测试用例：

package pag1;

public class SolutionListNode {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1=pHead1;
        ListNode cur2=pHead2;
        while(cur1!=cur2){
            cur1=(cur1==null? pHead2:cur1.next);
            cur2=(cur2==null? pHead1:cur2.next);
        }
        return cur1;
    }

    public static void main(String[] args) {
        SolutionListNode test=new SolutionListNode();

        ListNode head1 = new ListNode(1);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(3);
        ListNode forth = new ListNode(4);
        ListNode five = new ListNode(5);
        head1.next = second;
        second.next = third;
        third.next = forth;
        forth.next=five;

        five.next=null;//所谓的公共节点，一定是两个链表共用的节点，不能new一个新的节点出来。


        ListNode  head2=third;



        System.out.println(test.FindFirstCommonNode(head1, head2).val);
    }
}

方法四、运用HasnMap的特性参考：赵振江_12浪潮优派的解答

hashmap<key,value>分别存储node和null,

注意，即使node1.val=node2.val，但node1的地址和node2的地址不一样时，认为node1和node不一样，即对应的key不一样，所以链表用hashmap存储时不用担心会把某些节点合并。

 ListNode current1 = pHead1;
        ListNode current2 = pHead2;

        HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
        while (current1 != null) {
            hashMap.put(current1, null);
            current1 = current1.next;
        }
        while (current2 != null) {
            if (hashMap.containsKey(current2))
                return current2;
            current2 = current2.next;
        }

        return null;

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

题目描述

相关推荐