java 相交鏈表的實(shí)現(xiàn)示例
更新時(shí)間：2021年11月08日 09:14:59 作者：宗旨飛翔
本文主要介紹了java 相交鏈表的實(shí)現(xiàn)示例，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
1.題目
相交鏈表：給你兩個(gè)單鏈表的頭節(jié)點(diǎn) headA 和 headB ，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒有交點(diǎn)，返回 null 。相交鏈表
2.分析
相交鏈表是Y字型，next域相同。
定義兩個(gè)引用pl和ps，
如果每個(gè)鏈表相交結(jié)點(diǎn)前長度相同，一步一步走，直到相同就找到了相交結(jié)點(diǎn)。如果長度不一樣，首先要長鏈表先走差值步，然后再一人走一步直到相遇
長度不同：
長度相同：
首先求長度，先假設(shè)pl指向headA：
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null;
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null;
ps = headB;
然后根據(jù)長度差值的正負(fù)判斷誰長，將pl指向長的鏈表：
int len = lenA - lenB;//差值步
if (len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
然后長的先走長度差值步，最后一人一步走：
//pl走差值len步
while (len != 0) {
pl = pl.next;
len--;
}
//同時(shí)走，直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl;
}
3.完整代碼
//判斷鏈表相交
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null;
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null;
ps = headB;
int len = lenA - lenB;//差值步
if (len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
//1、pl永遠(yuǎn)指向最長的鏈表 ps永遠(yuǎn)指向最短的鏈表 2、求到了差值len步
//pl走差值len步
while (len != 0) {
pl = pl.next;
len--;
}
//同時(shí)走，直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl;
}
測(cè)試：
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
System.out.println("myLinkedList：");
myLinkedList.display();
MyLinkedList myLinkedList1 = new MyLinkedList();
myLinkedList1.addLast(13);
myLinkedList1.addLast(22);
myLinkedList1.addLast(30);
System.out.println("myLinkedList1：");
myLinkedList1.display();
createCut(myLinkedList.head, myLinkedList1.head);
try {
ListNode ret = getIntersectionNode(myLinkedList.head, myLinkedList1.head);
myLinkedList.display2(ret);
} catch (NullPointerException e) {
e.printStackTrace();
System.out.println("沒有相交結(jié)點(diǎn)！");
}
}
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(56);
System.out.println("myLinkedList:");
myLinkedList.display();
MyLinkedList myLinkedList1 = new MyLinkedList();
myLinkedList1.addLast(12);
myLinkedList1.addLast(23);
myLinkedList1.addLast(30);
System.out.println("myLinkedList1:");
myLinkedList1.display();
//createCut(myLinkedList.head,myLinkedList1.head);
try {
ListNode ret = getIntersectionNode(myLinkedList.head, myLinkedList1.head);
System.out.println(ret.val);
}catch (NullPointerException e){
e.printStackTrace();
System.out.println("不存在相交結(jié)點(diǎn)！");
}
}
到此這篇關(guān)于java 相交鏈表的實(shí)現(xiàn)示例的文章就介紹到這了,更多相關(guān)java 相交鏈表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Spring Boot中數(shù)據(jù)庫操作Druid和HikariDataSource的詳細(xì)過程
這篇文章主要介紹了Spring Boot中數(shù)據(jù)庫操作Druid和HikariDataSource的詳細(xì)過程,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-06-06
Java的Netty進(jìn)階之Future和Promise詳解
這篇文章主要介紹了Java的Netty進(jìn)階之Future和Promise詳解,Netty 是基于 Java NIO 的異步事件驅(qū)動(dòng)的網(wǎng)絡(luò)應(yīng)用框架,使用 Netty 可以快速開發(fā)網(wǎng)絡(luò)應(yīng)用,Netty 提供了高層次的抽象來簡化 TCP 和 UDP 服務(wù)器的編程,但是你仍然可以使用底層的 API,需要的朋友可以參考下2023-11-11
這篇文章主要介紹了Java 線程的相關(guān)資料，幫助大家更好的理解和學(xué)習(xí)使用Java，感興趣的朋友可以了解下2021-02-02
InteliJ IDEA 設(shè)置eclipse快捷鍵 的圖文教程
本文通過圖文并茂的形式給大家介紹了InteliJ IDEA 設(shè)置eclipse快捷鍵 ，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友參考下2018-06-06
這篇文章主要介紹了Java 停止線程需要注意的地方，幫助大家更好的理解和學(xué)習(xí)Java線程的相關(guān)資料，感興趣的朋友可以了解下2020-09-09
基于springboot實(shí)現(xiàn)數(shù)據(jù)可視化的示例代碼
本文主要介紹了基于springboot實(shí)現(xiàn)數(shù)據(jù)可視化，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧<BR>2022-07-07
@RequestBody時(shí)第二個(gè)字母大寫,映射不到的解決
這篇文章主要介紹了@RequestBody時(shí)第二個(gè)字母大寫，映射不到的解決方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
Jmeter如何將每次測(cè)試的結(jié)果保存到文件中
這篇文章主要介紹了Jmeter如何將每次測(cè)試的結(jié)果保存到文件中的問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-03-03
這篇文章主要介紹了Maven打包的相關(guān)知識(shí)，本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-09-09
關(guān)于網(wǎng)頁報(bào)錯(cuò)404原因以及解決方法
404錯(cuò)誤是網(wǎng)站常見的錯(cuò)誤之一,出現(xiàn)的原因很多,解決方法也有很多種,這篇文章主要給大家介紹了關(guān)于網(wǎng)頁報(bào)錯(cuò)404原因以及解決方法的相關(guān)資料,需要的朋友可以參考下2024-01-01