52-两个链表的第一个公共节点
大约 1 分钟
输入两个链表,找出它们的第一个公共结点
存在公共结点的链表是Y的形状。
![两个链表](http://daipeng.site/static/image/2020-03-28/1585389989257.jpg)
暴力解法
最容易想到的是暴力解法,在第一个链表上遍历节点,对每一个节点同时遍历第二个链表里的结点,如果相同说明是公共结点。
两个指针
我们假设两个链表有共同的一段链表,那么根据形状可以得知,可以用两个指针分别指向两个链表,然后让指向长链表的指针先走若干步,然后两个指针在共同的前进。
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int m = calListLength(headA);//计算长度
int n = calListLength(headB);//
if (m > n) {
int gap = m - n;
while (gap > 0) {
headA = headA.next;
gap--;
}
}else{
int gap = n - m;
while (gap > 0) {
headB = headB.next;
gap--;
}
}
//两个指针齐头并进
while (headA != null && headB != null) {
if (headA == headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
private int calListLength(ListNode head) {
ListNode first = head;
int m = 0;
while (first != null) {
m++;
first = first.next;
}
return m;
}
栈解法
我们可以分别遍历两个链表,将节点存储到两个栈中,然后从两个栈分别出栈,直到最后一个相同的结点就是第一个公共结点。
public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
Stack<ListNode> first = new Stack<>();
Stack<ListNode> second = new Stack<>();
while (headA != null) {
first.push(headA);
headA = headA.next;
}
while (headB != null) {
second.push(headB);
headB = headB.next;
}
ListNode same = null;
while (!first.isEmpty() && !second.isEmpty()) {
if (first.peek() == second.peek()) {
same = first.pop();
second.pop();
}else{
break;
}
}
return same;
}