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

- 1、题目描述：

- 2、题目链接：
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=188&tqId=38045&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-week%2Fquestion-ranking&tab=answerKey

-3、 设计思想：

详细操作流程看下图：

-4、视频讲解链接B站视频讲解

-5、代码：
c++版本:

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        if(pHead1 == nullptr || pHead2 == nullptr){
            //特判为空的情况
            return nullptr;
        }
        ListNode*cur1 = pHead1;
        ListNode*cur2 = pHead2;
        int n = 0;//用来保存两个链表长度差
        //找到链表最后一个元素，并且沿途更新n，用来判断链表谁长
        while(cur1->next){
            n ++;
            cur1 = cur1->next;
        }
        while(cur2->next){
            n --;
            cur2 = cur2->next;
        }
        //上面结束后n的含义代表两个链表的长度差
        if(cur1 != cur2){
            //如果最后一个元素都不相等，那么肯定没有公共节点
            return nullptr;
        }
        cur1 = n > 0 ? pHead1 : pHead2;//谁长谁就变成cur1
        cur2 = cur1 == pHead1 ? pHead2:pHead1;//谁短谁就是cur2
        n = abs(n);//如果为n<0需要变成正数
        while(n){
            //使cur1移动到和cur2长度一样的位置处
            n--;
            cur1 = cur1->next;
        }
        //此时,链表长度都是从同一长度出发，能够找到第一个公共节点
        while(cur1!=cur2){
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        return cur1;

    }
}; 

Java版本：

/*
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 cur1 = pHead1;
        ListNode cur2 = pHead2;
        int n = 0;//用来保存两个链表长度差
        //找到链表最后一个元素，并且沿途更新n，用来判断链表谁长
        while(cur1.next!= null){
            n ++;
            cur1 = cur1.next;
        }
        while(cur2.next!= null){
            n --;
            cur2 = cur2.next;
        }
        //上面结束后n的含义代表两个链表的长度差
        if(cur1 != cur2){
            //如果最后一个元素都不相等，那么肯定没有公共节点
            return null;
        }
        cur1 = n > 0? pHead1 : pHead2;//谁长谁就变成cur1
        cur2 = cur1 == pHead1 ? pHead2:pHead1;//谁短谁就是cur2
        n = Math.abs(n);//如果为n<0需要变成正数
        while(n > 0){
            //使cur1移动到和cur2长度一样的位置处
            n--;
            cur1 = cur1.next;
        }
        //此时,链表长度都是从同一长度出发，能够找到第一个公共节点
        while(cur1!=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}

Python版本:

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param pHead1 ListNode类 
# @param pHead2 ListNode类 
# @return ListNode类
#
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        # write code here
        if pHead1==None or pHead2 == None:
            #特判为空的情况
            return None
        cur1,cur2=pHead1,pHead2
        n = 0#用来保存两个链表长度差
        #找到链表最后一个元素，并且沿途更新n，用来判断链表谁长
        while cur1.next:
            n += 1
            cur1 = cur1.next
        while cur2.next:
            n -= 1
            cur2 = cur2.next
        #上面结束后n的含义代表两个链表的长度差 
        if cur1 != cur2:
            #如果最后一个元素都不相等，那么肯定没有公共节点
            return None
        cur1 = pHead1 if n > 0 else pHead2#谁长谁就变成cur1
        cur2 = pHead2 if cur1 == pHead1 else pHead1;#谁短谁就是cur2
        n = abs(n)#如果为n<0需要变成正数
        while n:
            #使cur1移动到和cur2长度一样的位置处
            n -= 1
            cur1 = cur1.next
        #此时,链表长度都是从同一长度出发，能够找到第一个公共节点
        while cur1!=cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        return cur1

JavaScript版本:

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
    // write code here
    if(pHead1 == null || pHead2 == null){
            //特判为空的情况
            return null;
        }
        let cur1 = pHead1;
        let cur2 = pHead2;
        let n = 0;//用来保存两个链表长度差
        //找到链表最后一个元素，并且沿途更新n，用来判断链表谁长
        while(cur1.next!= null){
            n ++;
            cur1 = cur1.next;
        }
        while(cur2.next!= null){
            n --;
            cur2 = cur2.next;
        }
        //上面结束后n的含义代表两个链表的长度差
        if(cur1 != cur2){
            //如果最后一个元素都不相等，那么肯定没有公共节点
            return null;
        }
        cur1 = n > 0? pHead1 : pHead2;//谁长谁就变成cur1
        cur2 = cur1 == pHead1 ? pHead2:pHead1;//谁短谁就是cur2
        n = Math.abs(n);//如果为n<0需要变成正数
        while(n > 0){
            //使cur1移动到和cur2长度一样的位置处
            n--;
            cur1 = cur1.next;
        }
        //此时,链表长度都是从同一长度出发，能够找到第一个公共节点
        while(cur1!=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};