生活随笔
收集整理的這篇文章主要介紹了
数据结构与算法--两个链表中第一个公共节点
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
鏈表中第一個公共節(jié)點
- 公節(jié)點定義：同一個節(jié)點在兩個鏈表中，并不是節(jié)點值相同
- 題目：輸入兩個節(jié)點，找出他們的第一個公共節(jié)點，節(jié)點定義如需
public class ListNode implements Comparable<ListNode> {private String key
;private Integer value
;private ListNode next
;private ListNode before
;...
-
本文中所有有關(guān)鏈表定義以及操作都使用自己實現(xiàn)的鏈表相關(guān)方法，如需看詳細(xì)實現(xiàn)可裝到對應(yīng)章節(jié)：數(shù)據(jù)結(jié)構(gòu)與算法–鏈表實現(xiàn)以及應(yīng)用
-
兩個單向鏈表，特點在于只能同頭開始遍歷，因此最簡單方案，還是雙循環(huán)，每次遍歷鏈表A的節(jié)點時候，與鏈表B中節(jié)點逐個比較，直到找到相同的節(jié)點問題
-
這種方法實現(xiàn)簡單，但是時間復(fù)雜度是最大的，如果A有m個階段，B有n個階段那么時間復(fù)雜度是O(mn)，應(yīng)該有更好的方案
-
方案二：
- 單向鏈表有共同節(jié)點，因為每個節(jié)點都是有一個next指針
- 因此從共同節(jié)點開始，之后的所有節(jié)點都是相同的，因此這個兩個鏈表應(yīng)該是個Y字形狀，如下圖
- 因為兩個鏈表可能節(jié)點個數(shù)不同，因此從頭開始遍歷不能直接得到，
- 那么如果從后開始遍歷，那邊一定就是相同的節(jié)點
- 如果能將鏈表反轉(zhuǎn)，從后向前遍歷，最后一個相同的節(jié)點就是我們需要求解的值，如下圖解
- 如上圖，第一個想到的方法是反轉(zhuǎn)鏈表，因為單向鏈表只能從頭開始，反轉(zhuǎn)后可以從尾部開始遍歷，反轉(zhuǎn)后出現(xiàn)如下情況：
- 當(dāng)修改第一個鏈表時候，第二個鏈表其實也被修改了，并且此時已經(jīng)找不到地兒個鏈表的尾部節(jié)點，因此方法是不成了。
- 還有另外方法，我們將鏈表的每個節(jié)點存儲到另外一個數(shù)組中，然后從數(shù)組尾部開始遍歷
- 那么用棧來存儲鏈表節(jié)點，此時是最適合的
- 遍歷兩個鏈表，分別存儲兩個棧，stack1， stack2,
- 接著遍歷stack1， stack2， 因為后進(jìn)先出，因此先處理的必然是相等的，我們只需要找到第一個不相等的節(jié)點
- 如下實現(xiàn)，此處對棧的定義以及相關(guān)方法的實現(xiàn)都是用的自己對棧的實現(xiàn)方法，可到之前對應(yīng)章節(jié)查看詳細(xì)的實現(xiàn)：數(shù)據(jù)結(jié)構(gòu)與算法–簡單棧實現(xiàn)及其應(yīng)用
public class FindFirstCommonNode {public static void main(String[] args
) {Random random
= new Random();Integer number1
= random
.nextInt(100);ListNode node1
= new ListNode(number1
.toString(), number1
);for (int i
= 0; i
< 3; i
++) {Integer number
= random
.nextInt(100);ListNode newNode
= new ListNode(number
.toString(), number
);MyLinkedList.addToTail(node1
, newNode
);}Integer number2
= random
.nextInt(100);ListNode node2
= new ListNode(number2
.toString(), number2
);for (int i
= 0; i
< 6; i
++) {Integer number
= random
.nextInt(100);ListNode newNode
= new ListNode(number
.toString(), number
);MyLinkedList.addToTail(node2
, newNode
);}ListNode node3
= new ListNode("x", 3);MyLinkedList.addToTail(node1
, node3
);MyLinkedList.addToTail(node2
, node3
);for (int i
= 0; i
< 3; i
++) {Integer number
= random
.nextInt(100);ListNode newNode
= new ListNode(number
.toString(), number
);MyLinkedList.addToTail(node1
, newNode
);}MyLinkedList.print(node1
);System.out
.println();MyLinkedList.print(node2
);ListNode commonNode
= findFirstCommonNodeStack(node1
, node2
);System.out
.println();System.out
.println(commonNode
.getKey());}public static ListNode findFirstCommonNodeStack(ListNode node1
, ListNode node2
) {if (node1
== null || node2
== null) {return null;}if (node1
.getNext() == null && node2
.getNext() == null) {return node1
.equals(node2
) ? node1
: null;}MyStack stack1
= new MyStack();ListNode head
= node1
;while (head
!= null) {stack1
.push(head
);head
= head
.getNext();}MyStack stack2
= new MyStack();head
= node2
;while (head
!= null) {stack2
.push(head
);head
= head
.getNext();}ListNode commonNode
= null;while (!stack1
.isEmpty() && !stack2
.isEmpty()) {ListNode popStack1
= (ListNode) stack1
.pop();ListNode popStack2
= (ListNode) stack2
.pop();if (popStack1
.equals(popStack2
)) {commonNode
= popStack1
;}}return commonNode
;}
}
public class FindFirstCommonNode {public static void main(String[] args
) {Random random
= new Random();Integer number1
= random
.nextInt(100);ListNode node1
= new ListNode(number1
.toString(), number1
);for (int i
= 0; i
< 3; i
++) {Integer number
= random
.nextInt(100);ListNode newNode
= new ListNode(number
.toString(), number
);MyLinkedList.addToTail(node1
, newNode
);}Integer number2
= random
.nextInt(100);ListNode node2
= new ListNode(number2
.toString(), number2
);for (int i
= 0; i
< 6; i
++) {Integer number
= random
.nextInt(100);ListNode newNode
= new ListNode(number
.toString(), number
);MyLinkedList.addToTail(node2
, newNode
);}ListNode node3
= new ListNode("x", 3);MyLinkedList.addToTail(node1
, node3
);MyLinkedList.addToTail(node2
, node3
);for (int i
= 0; i
< 3; i
++) {Integer number
= random
.nextInt(100);ListNode newNode
= new ListNode(number
.toString(), number
);MyLinkedList.addToTail(node1
, newNode
);}MyLinkedList.print(node1
);System.out
.println();MyLinkedList.print(node2
);System.out
.println();ListNode commonNode2
= findFirstCommonNode(node1
, node2
);System.out
.println(commonNode2
.getKey());}public static ListNode findFirstCommonNode(ListNode node1
, ListNode node2
){if (node1
== null || node2
== null) {return null;}if (node1
.getNext() == null && node2
.getNext() == null) {return node1
.equals(node2
) ? node1
: null;}Integer countNode1
= 0;ListNode header
= node1
;while (header
!= null){countNode1
++;header
= header
.getNext();}Integer countNode2
= 0;header
= node2
;while (header
!= null){countNode2
++;header
= header
.getNext();}Integer prefix
= Math.abs(countNode1
- countNode2
);ListNode header1
= node1
;ListNode header2
= node2
;if(countNode1
> countNode2
){for (int i
=0; i
< prefix
; i
++){if(header1
!= null){header1
= header1
.getNext();}}}else {for (int i
=0; i
< prefix
; i
++){if(header2
!= null){header2
= header2
.getNext();}}}while (header1
!= null && header2
!= null){if(header1
.equals(header2
)){return header1
;}header1
= header1
.getNext();header2
= header2
.getNext();}return null;}
}
- 方法三中沒有用到額外的存儲空間，時間復(fù)雜度同樣也是O(m+n)，要優(yōu)于方法二，這是目前想到的最優(yōu)方案。
上一篇：數(shù)據(jù)結(jié)構(gòu)與算法–數(shù)組中的逆序?qū)?br /> 下一篇：數(shù)據(jù)結(jié)構(gòu)與算法–最小的k個數(shù)
總結(jié)
以上是生活随笔為你收集整理的数据结构与算法--两个链表中第一个公共节点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
