网络推广和网站推广的关系,成都网站建设私单,wordpress推荐链接,网站开发包括网站设计面试题02.07.链表相交 两种解题思路 面试题02.07.链表相交一、双指针二、哈希集合 一、双指针
这道题简单来说#xff0c;就是求两个链表交点节点的指针
这里注意#xff1a;交点不是数值相等#xff0c;而是指针相等
为了方便举例#xff0c;假设节点元素数值相等…面试题02.07.链表相交 两种解题思路 面试题02.07.链表相交一、双指针二、哈希集合 一、双指针
这道题简单来说就是求两个链表交点节点的指针
这里注意交点不是数值相等而是指针相等
为了方便举例假设节点元素数值相等则节点指针相等
看如下两个链表如前curA指向链表A的头结点curB指向链表B的头结点 我们求出两个链表的长度并求出两个链表长度的差值然后让curA移动到和curB对齐的位置如图所示 此时我们就可以比较curA和curB是否相同如果不相同同时向后移动curA和curB如果遇到curAcurB则找到交点
否则循环退出返回空指针 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA headA;ListNode curB headB;int lenA 0,lenB 0;//求链表A的长度while(curA!null){lenA;curA curA.next;}//求链表B的长度while(curB!null){lenB;curB curB.next;}curA headA;curB headB;//让curA成为最长链表的头lenA为其长度if(lenBlenA){//交换lenA和lenB的值int tempLen 0;tempLen lenA;lenA lenB;lenB tempLen;//交换curA和curB指针ListNode tempNode curA;curA curB;curB tempNode;}//求长度差int gap lenA-lenB;//让curA和curB对齐while(gap0){curA curA.next;gap--;}//遍历curA和curB遇见相同val值则直接返回while(curA!null){//注意是指针相等if(curAcurB){return curA;}curA curA.next;curB curB.next;}return null;}二、哈希集合
判断两个链表是否相交可以使用哈希集合存储链表节点
首先遍历链表headA并将链表headA中的每个节点加入到哈希集合中
然后遍历链表headB对于遍历到的每个节点判断该节点是否在哈希集合中
如果当前节点不在哈希集合中则继续遍历下一个节点如果当前节点在哈希集合中则后面的节点都在哈希集合中即从当前节点开始的所有节点都在两个链表的相交部分因此在链表headB中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点返回该节点 public ListNode getIntersectionNode(ListNode headA, ListNode headB) {SetListNodevisited new HashSetListNode();ListNode temp headA;while(temp!null){visited.add(temp);temp temp.next;}temp headB;while(temp!null){if(visited.contains(temp)){return temp;}temp temp.next;}return null;}
