题目
编写一个程序,找到两个单链表相交的起始节点。
思路 + 代码
1. 最容易想到的,两层遍历求解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null || headB==null) return null; ListNode tmp; while(headA!=null){ tmp = headB; while(tmp!=null){ if(tmp!=headA) return tmp; tmp = tmp.next; } headA = headA.next; } return null; } }
|
时间复杂度O(M*N)
空间复杂度O(1)
2. 利用Map记录一个链表的每个节点,第二个链表寻找第一次出现的节点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null || headB==null) return null; Map<ListNode,Integer> map = new HashMap<ListNode,Integer>(); while(headA!=null){ map.put(headA,1); headA = headA.next; } while(headB!=null){ if(map.containsKey(headB)) return headB; headB = headB.next; } return null; } }
|
时间复杂度O(M+N)
空间复杂度O(M)或O(N)
3. 或者两个指针,分别从两个链表的头结点开始,当一个节点遍历到尾部时换到另一个链表头部。
即利用 a+all+b = b+all+a,也就是两个指针走的路程一样。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null || headB==null) return null; ListNode tmpA = headA; ListNode tmpB = headB; while(tmpA!=tmpB){ tmpA = tmpA==null?headB:tmpA.next; tmpB = tmpB==null?headA:tmpB.next; } return tmpA; return tmpA; } }
|
时间复杂度O(M+N)
空间复杂度O(1)