【剑指Offer】No.52 两个链表的第一个公共结点

第一个公共结点"/>

【剑指Offer】No.52 两个链表的第一个公共结点

题目描述

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

解题思路

链表的第一个公共结点之后的结点也一定是一样的即公共结点之后的长度相同，所以关键点在于知道两个链表的长度差是多少（假设为k），则较长的先走k步然后两个链表同时走并check结点是否相同即可。

/*
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 p = pHead1, q = pHead2;int l1 = 0, l2 = 0;while (p != null || q != null) {if (p != null) {l1++;p = p.next;}if (q != null) {l2++;q = q.next;}}p = pHead1;q = pHead2;if (l1 >= l2) {for (int i = 0; i < l1 - l2; i++) {p = p.next;}} else {for (int i = 0; i < l2 - l1; i++) {q = q.next;}}while (p != q) {p = p.next;q = q.next;}return p;}
}