美文网首页
剑指offer:两个链表的第一个公共结点

剑指offer:两个链表的第一个公共结点

作者: 衣介书生 | 来源:发表于2018-04-05 14:58 被阅读19次

题目分析

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

代码

/*
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;
        }
        
        // 统计两个链表的长度
        int l1 = 0;
        int l2 = 0;
        ListNode temp1 = pHead1;
        ListNode temp2 = pHead2;
        while(temp1 != null) {
            temp1 = temp1.next;
            l1 ++;
        }
        while(temp2 != null) {
            temp2 = temp2.next;
            l2 ++;
        }
        
        // 让长链表先走两链表长度差的绝对值步
        temp1 = pHead1;
        temp2 = pHead2;
        if(l1 >= l2) {
            for(int i = 0; i < l1 - l2; i++) {
                temp1 = temp1.next;
            }
        } else {
            for(int i = 0; i < l2 - l1; i++) {
                temp2 = temp2.next;
            }
        }
        while(temp1 != null) {
            if(temp1 == temp2) {
                return temp1;
            }
            temp1 = temp1.next;
            temp2 = temp2.next;
        }
        return null;
    }
}

相关文章

网友评论

      本文标题:剑指offer:两个链表的第一个公共结点

      本文链接:https://www.haomeiwen.com/subject/dypyfftx.html