成都创意设计公司苏州排名搜索优化

面试题 02.07. 链表相交

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

方法一：遍历headA，将每个节点add到HashSet中；然后遍历headB，如果HashSet contains当前节点则返回该节点。

此方法的时间复杂度为O(m+n), m为headA长度，n为headB长度;空间复杂度为O(m)，因为需要使用HashSet存储headA。

/*** 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) {HashSet<ListNode> visited = new HashSet<ListNode>();ListNode i = headA;while(i != null){visited.add(i);i = i.next;}i = headB;while(i != null){if(visited.contains(i)) return i;i = i.next;}return null;}
}

方法二：双指针法
eadA长度为m, headB长度为n，假设headA在相交节点之前长度为a，headB在相交节点之前长度为b，那么应有m+b = n+a，因此使用两个指针i，j分别遍历headA, headB，在一个链表遍历结束后去遍历另一链表，当i == j时候，返回i或j即可。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode a = headA;ListNode b = headB;ListNode ins = null;while(a != b){a = (a != null) ? a.next : headB;b = (b != null) ? b.next : headA;ins = a;}return ins;}
}