資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Java 中查詢兩個連結串列的交點
連結串列是一種線性資料結構，其中每個節點有兩個塊，一個塊包含節點的值或資料，另一個塊包含下一個節點的地址。
假設我們有一個連結串列，每個節點包含一個隨機指標，該指標指向列表中的其他節點。任務是找到兩個連結串列相互交叉的節點。如果它們不相交，則返回 NULL 或空作為輸出。
例如
輸入 1
輸出
2
說明：由於給定的連結串列在值為“2”的節點處相交，因此我們將返回“2”作為輸出。
輸入 2
輸出
NULL
說明：由於沒有公共點，因此在這種情況下我們將返回 NULL。
解決此問題的方法
我們有兩個連結串列，它們在某個公共點處相交。為了找到交點，我們將遍歷兩個連結串列，直到我們發現它們都指向相同的值。在某個點，連結串列的下一個節點的指標將相同。因此，我們將返回該點的值。
- 使用兩個連結串列，分別包含資料和指向下一個節點的指標。
- 函式 commonPoint(listnode*headA, listnode*headB) 分別接受兩個連結串列指標，並返回連結串列的公共點或交點的值。
- 一個查詢連結串列長度的整型函式將返回從列表頭部開始的兩個連結串列的長度。
- 現在建立一個指向兩個列表頭的指標，並遍歷長度較長的列表，直到 (第一個列表的長度 - 第二個列表的長度)。
- 現在遍歷列表，直到我們找到下一個指標相等。
- 返回兩個列表相交的特定節點的值。
示例
public class Solution {
static listnode headA,
headB;
static class listnode {
int data;
listnode next;
listnode(int d) {
data = d;
next = null;
}
}
int count(listnode head) {
int c = 0;
while (head != null) {
c++;
head = head.next;
}
return c;
}
int commonPoint(listnode headA, listnode headB) {
listnode p1 = headA;
listnode p2 = headB;
int c1 = count(headA);
int c2 = count(headB);
if (c1 > c2) {
for (int i = 0; i < c1 - c2; i++) {
if (p1 == null) {
return - 1;
}
p1 = p1.next;
}
}
if (c1 < c2) {
for (int i = 0; i < c2 - c1; i++) {
if (p2 == null) {
return - 1;
}
p2 = p2.next;
}
}
while (p1 != null && p2 != null) {
if (p1.data == p2.data) {
return p1.data;
}
p1 = p1.next;
p2 = p2.next;
}
return - 1;
}
public static void main(String[] args) {
Solution list = new Solution();
list.headA = new listnode(5);
list.headA.next = new listnode(4);
list.headA.next.next = new listnode(9);
list.headA.next.next.next = new listnode(7);
list.headA.next.next.next.next = new listnode(1);
list.headB = new listnode(6);
list.headB.next = new listnode(7);
list.headB.next.next = new listnode(1);
System.out.println(list.commonPoint(headA, headB));
}
}執行以上程式碼將生成以下輸出：
輸出
7
說明：給定的連結串列在 7 處相交。
更新於： 2021-02-23
547 次瀏覽
廣告