一定要早日上岸鸭 · July 17, 2021 0

160. 相交链表

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { // 哈希表做法: // public ListNode getIntersectionNode(ListNode headA, ListNode headB) { // Map <ListNode, Integer> hm = new HashMap<ListNode, Integer>(); // ListNode dummyA = new ListNode(); // ListNode dummyB = new ListNode(); // dummyA.next = headA; // dummyB.next = headB; // while(dummyA!=null){ // dummyA = dummyA.next; // int k = hm.getOrDefault(dummyA, 1); // hm.put(dummyA, k); // } // while(dummyB!=null){ // dummyB = dummyB.next; // int k = hm.getOrDefault(dummyB, 1); // hm.merge(dummyB, k, (oldValue, newValue) -> oldValue + newValue); // if(hm.get(dummyB)>1) return dummyB; // } // return null; // } // 双指针做法: // 思路是两根指针都经过了同样的距离(两圈)所以必定会在交点相遇 // ^因为ptrA到头后换到了headB,ptrB到头后换到了A public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA==null || headB==null) return null; ListNode ptrA=headA, ptrB=headB; while(ptrA!=ptrB){ ptrA = ptrA.next; ptrB = ptrB.next; if(ptrA==null && ptrB==null) return null; if(ptrA==null){ ptrA = headB; } if(ptrB==null){ ptrB = headA; } } return ptrA; } }