題目描述
給你兩個單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請你找出并返回兩個單鏈表相交的起始節(jié)點(diǎn)。如果兩個鏈表不存在相交節(jié)點(diǎn)，返回 null
示例1:
輸入：listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
輸出：Intersected at '8'
解釋：相交節(jié)點(diǎn)的值為 8 。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節(jié)點(diǎn)前有 2 個節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個節(jié)點(diǎn)。
示例2:
輸入：listA = [1,9,1,2,4], listB = [3,2,4]
輸出：Intersected at '2'
解釋：相交節(jié)點(diǎn)的值為 2 。
從各自的表頭開始算起，鏈表 A 為 [1,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點(diǎn)前有 3 個節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 1 個節(jié)點(diǎn)。
示例3:
輸入：listA = [2,6,4], listB = [1,5]
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
這兩個鏈表不相交，因此返回 null
題解
思路1: 哈希集合
判斷兩個鏈表是否相交，可以使用哈希集合存儲鏈表節(jié)點(diǎn)。
首先遍歷鏈表headA，并將鏈表headA 中的每個節(jié)點(diǎn)加入哈希集合中。然后遍歷鏈表headB，對于遍歷到的每個節(jié)點(diǎn)，判斷該節(jié)點(diǎn)是否在哈希集合中：
如果當(dāng)前節(jié)點(diǎn)不在哈希集合中，則繼續(xù)遍歷下一個節(jié)點(diǎn)；
如果當(dāng)前節(jié)點(diǎn)在哈希集合中，則后面的節(jié)點(diǎn)都在哈希集合中，即從當(dāng)前節(jié)點(diǎn)開始的所有節(jié)點(diǎn)都在兩個鏈表的相交部分，因此在鏈表headB 中遍歷到的第一個在哈希集合中的節(jié)點(diǎn)就是兩個鏈表相交的節(jié)點(diǎn)，返回該節(jié)點(diǎn)。
如果鏈表headB 中的所有節(jié)點(diǎn)都不在哈希集合中，則兩個鏈表不相交，返回null
// OC
+ (ListNode *)getIntersectionNode1:(ListNode *)headA headB:(ListNode *)headB {
NSMutableArray *hashArrayA = [[NSMutableArray alloc] init];
ListNode *curA = headA;
while (curA != nil) {
[hashArrayA addObject:curA];
curA = curA.next;
}
ListNode *curB = headB;
while (curB != nil) {
if ([hashArrayA containsObject:curB]) {
return curB;
}
curB = curB.next;
}
return nil;
}
// Swift
static public func getIntersectionNode1(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
var listA = [ListNode]()
var cura = headA
while cura != nil {
listA.append(cura!)
cura = cura?.next
}
var curb = headB
while curb != nil {
if listA.contains(curb!) {
return curb
}
curb = curb?.next
}
return nil
}
extension ListNode: Hashable, Equatable {
public func hash(into hasher: inout Hasher) {
// 用于唯一標(biāo)識
hasher.combine(val)
hasher.combine(ObjectIdentifier(self))
}
public static func ==(lhs: ListNode, rhs: ListNode) -> Bool {
return lhs === rhs
}
}
思路2: 雙指針
如果兩個鏈表節(jié)點(diǎn)數(shù)相等，則直接遍歷兩個鏈表相同位置是否相同
如果兩個鏈表節(jié)點(diǎn)數(shù)不相等，令鏈表headA的節(jié)點(diǎn)數(shù)為x，鏈表headB的節(jié)點(diǎn)數(shù)為y，
假設(shè)x<y,如果我們將headB的末尾y-x個節(jié)點(diǎn)添加到headA的前面,令新headA為newHeadA，那么newHeadA的節(jié)點(diǎn)數(shù)為x+y-x 為y，headB的節(jié)點(diǎn)數(shù)也為y。
現(xiàn)在newHeadA的節(jié)點(diǎn)組成是headB末尾的y-x個節(jié)點(diǎn)+x個headA的原始節(jié)點(diǎn)，headB末尾的y-x個節(jié)點(diǎn)和headB頭部的y-x節(jié)點(diǎn)一定不相同，如果相同headB就一定存在環(huán)，可以自己畫下圖。
因而直接遍歷newHeadA、headB得到的結(jié)果和遍歷原始headA、headB的結(jié)果是一致的
那么我們又如何將headB的末尾y-x個節(jié)點(diǎn)添加到headA的前面？
很容易想到的方法是分別遍歷兩個鏈表，獲得它們各自的節(jié)點(diǎn)數(shù)，然后再遍歷headB，將headB的末尾y-x個節(jié)點(diǎn)添加到headA的前面，再同時遍歷newHeadA 和 headB，比較相同位置是否相同。
但這樣的話，就有4個單獨(dú)的while循環(huán)，時間復(fù)雜度就上去了，此方法不可取。
并且如果我們已經(jīng)獲取到headA、headB的節(jié)點(diǎn)數(shù)，我們可以直接同時遍歷headA、headB，在遍歷時先將headB的前y-x個節(jié)點(diǎn)移除，再比較相同位置是否相同。
headA的節(jié)點(diǎn)數(shù)x小于headB的節(jié)點(diǎn)數(shù)y，如果同時遍歷pA(pA初始化為headA)、pB(pB初始化為headB)，那么pA 為nil時，pB末尾還有y-x個節(jié)點(diǎn)。因而我們只需要在pA=nil時令pA=headB，pB為nil時令pB=headA即可
當(dāng)鏈表headA 和headB 都不為空時，創(chuàng)建兩個指針pA 和pB，初始時分別指向兩個鏈表的頭節(jié)點(diǎn)headA 和headB，然后將兩個指針依次遍歷兩個鏈表的每個節(jié)點(diǎn)。具體做法如下：
每步操作需要同時更新指針pA 和pB。
如果指針pA 不為空，則將指針pA 移到下一個節(jié)點(diǎn)；如果指針pB 不為空，則將指針pB 移到下一個節(jié)點(diǎn)。
如果指針pA 為空，則將指針pA 移到鏈表headB 的頭節(jié)點(diǎn)；
如果指針pB 為空，則將指針pB 移到鏈表headA 的頭節(jié)點(diǎn)。
當(dāng)指針pA 和pB 指向同一個節(jié)點(diǎn)或者都為空時，返回它們指向的節(jié)點(diǎn)或者null
證明下：
情況一：兩個鏈表相交
鏈表headA 和headB 的長度分別是m和n。假設(shè)鏈表headA 的不相交部分有a個節(jié)點(diǎn)，鏈表headB 的不相交部分有b 個節(jié)點(diǎn)，兩個鏈表相交的部分有c 個節(jié)點(diǎn)，則有a+c=m，b+c=n。
如果a=b，則兩個指針會同時到達(dá)兩個鏈表相交的節(jié)點(diǎn)，此時返回相交的節(jié)點(diǎn)；
如果a≠b，則指針pA會遍歷完鏈表headA，指針pB會后遍歷完鏈表headB，兩個指針不會同時到達(dá)鏈表的尾節(jié)點(diǎn)，然后指針pA移到鏈表headB 的頭節(jié)點(diǎn)，指針pB移到鏈表headA的頭節(jié)點(diǎn)，然后兩個指針繼續(xù)移動，在指針pA 移動了a+c+b 次、指針pB 移動了b+c+a 次之后，兩個指針會同時到達(dá)兩個鏈表相交的節(jié)點(diǎn)，該節(jié)點(diǎn)也是兩個指針第一次同時指向的節(jié)點(diǎn)，此時返回相交的節(jié)點(diǎn)。
情況二：兩個鏈表不相交
鏈表headA 和headB 的長度分別是m 和n?？紤]當(dāng)m=n和m≠n時，兩個指針分別會如何移動：
如果m=n，則兩個指針會同時到達(dá)兩個鏈表的尾節(jié)點(diǎn)，然后同時變成空值null，此時返回null；
如果m≠n，則由于兩個鏈表沒有公共節(jié)點(diǎn)，兩個指針也不會同時到達(dá)兩個鏈表的尾節(jié)點(diǎn)，因此兩個指針都會遍歷完兩個鏈表，在指針pA 移動了m+n 次、指針pB 移動了n+m 次之后，兩個指針會同時變成空值null，此時返回null。
// OC
+ (ListNode *)getIntersectionNode2:(ListNode *)headA headB:(ListNode *)headB {
if (headA == nil || headB == nil) {
return nil;
}
ListNode *pA = headA;
ListNode *pB = headB;
while (pA != pB) {
pA = (pA == nil) ? headB : pA.next;
pB = (pB == nil) ? headA : pB.next;
}
return pA;
}
// Swift
static public func getIntersectionNode2(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
var pA = headA
var pB = headB
while pA !== pB {
pA = (pA != nil) ? pA?.next : headB
pB = (pB != nil) ? pB?.next : headA
}
return pA
}
參考：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/
