题目描述:输入两个链表,找出它们的第一个公共结点。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
本来使用HashMap写的,后来看了题解,说是用HashMap违背了这道题的本意;
分析:
链表A:3->5->1->8->2->0;
链表B:6->8->2->0;
链表A、B第一个公共节点是8,使用双指针遍历,遍历同时遍历;
链表A+B:3->5->1->8->2->0 + 6->8->2->0;
链表B+A:6->8->2->0 + 3->5->1->8->2->0;
可以看到两个指针会同时到最后一个8节点;
public class Solution { public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) { ListNode p1 = pHead1; ListNode p2 = pHead2; if(p1 == null || p2 == null) return null; while(p1 != p2){ p1 = p1.next; p2 = p2.next; // 如果p1 p2长度一样,并且遍历结束都没有相等的节点,返回null; if(p1 == null && p2 == null) return null; // 如果p1遍历结束,将链表B赋值给它 if(p1 == null) p1 = pHead2; // 如果p2遍历结束,将链表A赋值给它 if(p2 == null) p2 = pHead1; } return p1; } }