题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindFirstCommonNodeV1(ListNode pHead1, ListNode pHead2) { Deque<ListNode> queue = new LinkedList<>(); while (pHead1 != null) { queue.add(pHead1); pHead1 = pHead1.next; } while (pHead2 != null) { if (queue.contains(pHead2)) { return pHead2; } pHead2 = pHead2.next; } return null; } public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { int lengthA = 0; int lengthB = 0; ListNode pHeadA = pHead1; ListNode pHeadB = pHead2; while (pHeadA != null) { pHeadA = pHeadA.next; lengthA++; } while (pHeadB != null) { pHeadB = pHeadB.next; lengthB++; } pHeadA = pHead1; pHeadB = pHead2; //长的链表先走 if (lengthA > lengthB) { for (int i = 0; i < lengthA - lengthB; i++) { pHeadA = pHeadA.next; } } else { for (int i = 0; i < lengthB - lengthA; i++) { pHeadB = pHeadB.next; } } //同时向前移动指针,直到相等。若到尾节点,则没有相同的。 while (pHeadA != pHeadB) { pHeadA = pHeadA.next; pHeadB = pHeadB.next; } return pHeadA; } }