【链表5】两个链表的第一个公共结点

题目描述

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

如：链表1：1>>>2>>>3>>6>>>7     

链表2： 4>>>5>>6>>>7

最优解：

交叉遍历两个链表，寻找公共节点：

/*
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 node1 = pHead1;
        ListNode node2 = pHead2;
        while(node1 != node2) {
            node1 = node1 == null ? pHead2 : node1.next;
            node2 = node2 == null ? pHead1 : node2.next;
        }
        return node2;
    }
}

方法一：

  两个链表公共结点为6.如何获取？先让链表走一步(即长链表比短链表多的部分)，这时长链表指针在2位置，短链表在4位置。

然后一起走，碰到第一个相等的数(6)，即为第一个公共结点。

/*
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;
        
        ListNode firstCommonNode = null;
        int len1 = getLenOfListNode(pHead1);
        int len2 = getLenOfListNode(pHead2);
        
        int dif = len1 > len2 ? (len1 - len2) : (len2 - len1);
        ListNode fast =  len1 > len2 ? pHead1 : pHead2;
        ListNode slow =  len1 < len2 ? pHead1 : pHead2;
        
        for(int i = 0; i < dif; i++){
            fast = fast.next;
        }
        
        while(slow != null && fast != null){
            if(slow.val == fast.val)
                return slow;
            slow = slow.next;
            fast = fast.next;
        }
        
        return null;
    }
    
    //获取链表长度
    private int getLenOfListNode(ListNode pHead){
        if(pHead == null)
            return 0;
        int len =0 ;
        while(pHead != null){
            len++;
            pHead = pHead.next;
        }
        return len;
    }
    
    
}

方法二：用HashSet

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

    ListNode(int val) {
        this.val = val;
    }
}*/
import java.util.*;

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
 
        if(pHead1 ==  null ||pHead2==null)
            return null;
        Set<ListNode> set = new HashSet<>();
        //先加入链表1 中的结点
        while(pHead1 != null){
           set.add(pHead1); 
           pHead1 =  pHead1.next;
        }
        
        //同时加入结点2中的元素，如果set.add(pHead2)为false,则代表此元素为两链表公共结点
        while(pHead2 != null && set.add(pHead2)){
           pHead2 =  pHead2.next;
        }
        return pHead2;
        
    }
}

方法三：

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    private int getLenOfListNode(ListNode pHead){
        int count = 0;
        while(pHead != null){
            count++;
            pHead = pHead.next;
        }
        return count;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if(pHead1 == null || pHead2 == null)
            return null;
        
        ListNode firstCommonNode = null;
        int len1 = getLenOfListNode(pHead1);
        int len2 = getLenOfListNode(pHead2);
        
        int dif = len1 > len2 ? (len1 - len2) : (len2 - len1);
        ListNode fast =  len1 > len2 ? pHead1 : pHead2;
        ListNode slow =  len1 < len2 ? pHead1 : pHead2;
        
        for(int i = 0; i < dif; i++){
            fast = fast.next;
        }
        
        while(slow != null && fast != null){
            if(slow.val == fast.val)
                return slow;
            slow = slow.next;
            fast = fast.next;
        }
        
        return null;
    }
}