面試題 02.07. 鏈表相交

給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回 null 。

方法一：遍歷headA，將每個(gè)節(jié)點(diǎn)add到HashSet中；然后遍歷headB，如果HashSet contains當(dāng)前節(jié)點(diǎn)則返回該節(jié)點(diǎn)。

此方法的時(shí)間復(fù)雜度為O(m+n), m為headA長(zhǎng)度，n為headB長(zhǎng)度;空間復(fù)雜度為O(m)，因?yàn)樾枰褂肏ashSet存儲(chǔ)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;}
}

方法二：雙指針?lè)?br /> eadA長(zhǎng)度為m, headB長(zhǎng)度為n，假設(shè)headA在相交節(jié)點(diǎn)之前長(zhǎng)度為a，headB在相交節(jié)點(diǎn)之前長(zhǎng)度為b，那么應(yīng)有m+b = n+a，因此使用兩個(gè)指針i，j分別遍歷headA, headB，在一個(gè)鏈表遍歷結(jié)束后去遍歷另一鏈表，當(dāng)i == j時(shí)候，返回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;}
}