输入两个链表,找出它们的第一个公共结点(保证一定存在公共结点)
假设两个链表结构如图所示,最简单的想法就是:让长的链表先走,走完两个链表的长度差,然后再一起走
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1 == null || pHead2 == null) {
return null;
}
int length1 = getLength(pHead1);
int length2 = getLength(pHead2);
ListNode curNode1 = pHead1;
ListNode curNode2 = pHead2;
if(length1 >= length2) {
int len = length1 - length2;
while(len > 0) {
curNode1 = curNode1.next;
len--;
}
}
if(length2 > length1) {
int len = length2 - length1;
while(len > 0) {
curNode2 = curNode2.next;
len--;
}
}
while(curNode1 != curNode2) {
curNode1 = curNode1.next;
curNode2 = curNode2.next;
}
return curNode1;
}
public int getLength(ListNode pHead) {
int count = 0;
ListNode curNode = pHead;
while(curNode != null) {
count++;
curNode = curNode.next;
}
return count;
}
}
上一种做法使用了差值来让链表长度相同,也可以用别的方法。假设链表 A 长度为 a, 链表 B 的长度为 b,此时 a != b,但是,a + b == b + a
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode curNode1 = pHead1;
ListNode curNode2 = pHead2;
while(curNode1 != curNode2) {
curNode1 = curNode1 == null ? pHead2 : curNode1.next;
curNode2 = curNode2 == null ? pHead1 : curNode2.next;
}
return curNode1;
}
}
也可以运用 HashMap 的特性帮助解题
import java.util.HashMap;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode curNode1 = pHead1;
ListNode curNode2 = pHead2;
HashMap<ListNode, Integer> hashMap = new HashMap<ListNode, Integer>();
while (curNode1 != null) {
hashMap.put(curNode1, null);
curNode1 = curNode1.next;
}
while (curNode2 != null) {
if (hashMap.containsKey(curNode2))
return curNode2;
curNode2 = curNode2.next;
}
return null;
}
}
联系客服