我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 160. 相交鏈表
題目
撰寫一個程式，找到兩個單鏈表相交的起始節點，
如下面的兩個鏈表：
在節點 c1 開始相交，
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Reference of the node with value = https://www.cnblogs.com/izhoujie/p/8
輸入解釋：相交節點的值為 8 （注意，如果兩個鏈表相交則不能為 0），從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]，在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點，
示例 2：
輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Reference of the node with value = https://www.cnblogs.com/izhoujie/p/2
輸入解釋：相交節點的值為 2 （注意，如果兩個鏈表相交則不能為 0），從各自的表頭開始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]，在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點，
示例 3：
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
輸入解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]，由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值，
解釋：這兩個鏈表不相交，因此回傳 null，
注意：
- 如果兩個鏈表沒有交點，回傳 null.
- 在回傳結果后，兩個鏈表仍須保持原有的結構，
- 可假定整個鏈表結構中沒有回圈，
- 程式盡量滿足 O(n) 時間復雜度，且僅用 O(1) 記憶體，
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-兩次遍歷，一次求長度差然后對齊開始第二次遍歷并校驗交點
步驟：
- 各遍歷一次鏈表，求兩者的長度差；
- 長的鏈表先走差值個節點，然后兩個鏈表同步next并校驗next是否相同，相同即表示找到了交點，否則最終為null；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
思路2-兩次遍歷，但是設計上是兩個鏈表首位相接
思路決議：代碼的寫法等價于在各自鏈表的末尾拼接了另一個鏈表，代碼短簡且優雅；
這樣的拼接首先解決了鏈表的長度差，拼接后的長度一樣，遍歷時的情況：
- 兩個鏈表原長度一樣：
- 無交點，則在尾部時null==null，退出回圈，無需遍歷拼接部分；
- 有交點，則在到達尾部之前即可找到交點退出； - 兩個鏈表原長度不一樣：
- 無交點，則在遍歷完自身后在遍歷到拼接鏈表的尾部時有null==null，退出回圈；
- 有交點，則在遍歷完自身后在遍歷拼接鏈表時相當于思路1的對齊，兩指標必同時遍歷到交點然后退出回圈；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月19日 下午1:26:38
* @Description: 160. 相交鏈表
*
*/
public class LeetCode_0160 {
}
// Definition for singly-linked list.
class ListNode_0160 {
int val;
ListNode_0160 next;
ListNode_0160(int x) {
val = x;
next = null;
}
}
class Solution_0160 {
/**
* @author: ZhouJie
* @date: 2020年5月19日 下午1:32:36
* @param: @param headA
* @param: @param headB
* @param: @return
* @return: ListNode_0160
* @Description: 1-鏈表各需要遍歷兩次，一次統計長度，然后讓長的先移動比短的多出的節點數，最后一起移動找相同節點；
*
*/
public ListNode_0160 getIntersectionNode_1(ListNode_0160 headA, ListNode_0160 headB) {
if (headA == null || headB == null) {
return null;
}
int a = 0, b = 0;
ListNode_0160 A = headA, B = headB;
// 統計鏈表長度
while (headA != null) {
a++;
headA = headA.next;
}
while (headB != null) {
b++;
headB = headB.next;
}
// 鏈表頭對齊
if (a > b) {
a -= b;
while (a-- > 0) {
A = A.next;
}
} else if (a < b) {
b -= a;
while (b-- > 0) {
B = B.next;
}
}
// 尋找相交點，有則回傳相交點，無則回傳null
while (A != B) {
A = A.next;
B = B.next;
}
return A;
}
/**
* @author: ZhouJie
* @date: 2020年5月19日 下午1:44:52
* @param: @param headA
* @param: @param headB
* @param: @return
* @return: ListNode_0160
* @Description: 2-對方法1的優化
*
*/
public ListNode_0160 getIntersectionNode_2(ListNode_0160 headA, ListNode_0160 headB) {
if (headA == null || headB == null) {
return null;
}
ListNode_0160 A = headA, B = headB;
// 這里實際上相當于在A鏈表后面拼接了一個B鏈表，在B鏈表后面拼接了一個A鏈表，這樣就保證了兩個鏈表都有了相同的長度
// 且最多遍歷兩次即可得到結果
while (A != B) {
A = A == null ? headB : A.next;
B = B == null ? headA : B.next;
}
return A;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/185735.html
標籤：Java