兩個單鏈表相交的一系列問題
在本題中，單鏈表可能有環(huán)，也可能無環(huán)。給定兩個單鏈表的頭節(jié)點 head1 和 head2，這兩個鏈表可能相交，也可能
不相交。請實現(xiàn)一個函數(shù)，如果兩個鏈表相交，請返回相交的第一個節(jié)點；如果不相交，返回 null 即可。
如果鏈表 1 的長度為 N，鏈表 2 的長度為 M，時間復(fù)雜度請達到 O(N+M)，額外空間復(fù)雜度請達到 O(1)。（界定啊相交是內(nèi)存地址相同）


方法：哈希表（極簡單適用一切情況）依次遍歷，每遍歷一個節(jié)點，將其加入哈希表中，若遍歷到鏈表最后一個節(jié)點也沒有發(fā)現(xiàn)哈希表中有之前已經(jīng)記錄的節(jié)點，則表示鏈表無環(huán)，若遍歷到某個節(jié)點發(fā)現(xiàn)哈希表中已經(jīng)存過這個節(jié)點，則表示有環(huán)，且這個節(jié)點是第一個相交的節(jié)點。另一種方法，建立兩個指針，一個快指針，一個慢指針，慢指針依次遍歷鏈表中每個節(jié)點，快指針跳步前進，每次走兩個節(jié)點，則這兩個指針一定會在環(huán)中相遇，當(dāng)兩個指針相遇時，在鏈表開頭再設(shè)置一個指針，開頭的指針跟慢指針都繼續(xù)移動，每次一步，則兩個指針一定能在第一個環(huán)節(jié)點相遇


一個有環(huán)，一個無環(huán)，不可能相交
兩個無環(huán)鏈表，可以相交，有兩種結(jié)構(gòu)（“||”和“Y”，不可能是“X”）不用哈希表的方法：分別得到兩個鏈表的長度，若一個長度為50，一個長度為40，則較長的鏈表的指針先走10個節(jié)點，之后兩個鏈表的指針同步前進，若出現(xiàn)某時刻兩個指針相等，則表示相交,即“Y”，否則兩鏈表結(jié)構(gòu)是“||”
兩個鏈表都有環(huán)：
兩個鏈表各自都有環(huán)，沒有相交，即“66”結(jié)構(gòu)
兩個鏈表在環(huán)外相交，即
Y
O
若兩個鏈表的入環(huán)節(jié)點是同一個，則表示是“YO”結(jié)構(gòu)，則求第一個相交節(jié)點與“Y”情況解法相同
兩個鏈表共享環(huán)，即
||
O

兩個鏈表的指針，從頭開始，若Node1走到自身的節(jié)點也沒有遇到Node2，則表示兩個鏈表無交點，是“66”結(jié)構(gòu)，若兩個鏈表的指針在遇到自身節(jié)點之前遇到了另一個鏈表的節(jié)點，則表示“||O”結(jié)構(gòu)

public static class Node{public int value;public Node next;public Node(int data){this.value = data;} }public static Node getIntersectNode(Node haed1,Node head2){if(head1 == null || head2 == null){return null;}Node loop1 = getLoopNode(head1);Node loop2 = getLoopNode(head2);if(loop1 == null && loop2 == null){return noLoop(head1, head2);}if(loop1 != null && loop2 != null){return bothLoop(head1, loop1, head2, loop2);}return null; }public static Node getLoopNode(Node head){if(head == null || head.next == null || head.next.next == null){return null;}Node n1 = head.next; //n1為慢指針Node n2 = head.next.next; //n2為快指針while(n1 != n2){if(n2.next == null || n2.next.next == null){return null;}n2 = n2.next.next;n1 = n1.next;}n2 = head;while(n1 != n2){n1 = n1.next;n2 = n2.next;}n2 = head; //n2 從頭重新開始走，且變?yōu)槁羔榳hile(n1 != n2){n1 = n1.next;n2 = n2.next;}return n1; }public static Node noLoop(Node head1, Node head2){if(head1 == null || head2 == null){return null;}Node cur1 = head1;Node cur2 = head2;int n = 0;while(cur1.next != null){n++;cur1 = cur1.next;}while(cur2.next != null){n--;cur2 = cur2.next;}if(cur1 != cur2){return null;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while(n != 0){n--;cur1 = cur1.next;}while(cur1 != cur2){cur1 = cur1.next;cur2 = cur2.next;}return cur1; }public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2){Node cur1 = null;Node cur2 = null;if(loop1 == loop2){cur1 = head1;cur2 = head2;int n = 0;while(cur1 != loop1){n++;cur1 = cur1.next;}while(cur2 != loop2){n--;cur2 = cur2.next;}return cur1;}else{cur1 = loop1.next;while(cur1 != loop1){if(cur1 == loop2){return loop1;}cur1 = cur1.next;}return null;} }

總結(jié)

以上是生活随笔為你收集整理的两个单链表相交的一系列问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。