Leetcode相交链表(160)

问题

编写一个程序，找到两个单链表相交的起始节点。

方法

方法1

如果链表相交，那么相交节点的地址是一样的。

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { HashSet<ListNode> set = new HashSet<ListNode>(); //HashSet是无序唯一的 ListNode head1 = headA; ListNode head2 = headB; while(head1 != null) { //将a链表的节点全部添加到set中 set.add(head1); head1 = head1.next; } while(head2 != null) { //判断是否有相同的，两个链表相交，那么相交节点的地址是一样的 if(!set.contains(head2)) { set.add(head2); head2 = head2.next; } else { //返回相交节点 return head2; } } return null; //没有相交节点，返回null } }

这种方法的时间复杂度为O(m+n)，空间复杂度为O(n)或O(m)。

方法2

这个方法利用的是数学知识。使用一个指针从链表A的头部开始遍历整个链表A，然后从链表B的头部开始继续遍历，同样的使用另外一个指针从链表B的头部开始遍历，遍历完B以后从链表A的头部开始遍历，如果链表A和B相交的话，那么它们会在相交的节点相遇，此时对于从链表A开始遍历的指针有b+c+a，对于从链表B开始遍历的指针有a+c+b，可以看到两个指针遍历过的节点数是一样的。

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode l1 = headA, l2 = headB; while(l1 != l2) { //如果找到相交节点就退出循环 if(l1 == null) { //如果遍历完A就遍历B l1 = headB; } else { //继续遍历 l1 = l1.next; } if(l2 == null) { //如果遍历完B就遍历A l2 = headA; } else { l2 = l2.next; } } return l1; //返回相交节点 } }

这种方法的时间复杂度为O((a+b+c)*2)，空间复杂度为O(1)。

参考

Leetcode题解