Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
Credits:Special thanks to @stellari for adding this problem and creating all test cases.
Subscribe to see which companies asked this question.
題目
請(qǐng)寫一個(gè)程序，找到兩個(gè)單鏈表最開始的交叉節(jié)點(diǎn)。
** 注意事項(xiàng) **
如果兩個(gè)鏈表沒有交叉暮刃，返回null。
在返回結(jié)果后右钾，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。
可假定整個(gè)鏈表結(jié)構(gòu)中沒有循環(huán)旱爆。
樣例
下列兩個(gè)鏈表：
分析
這道題有兩種解法
容易想到的第一種解法舀射，先求出AB兩個(gè)鏈表的長(zhǎng)度，求出長(zhǎng)度的差值怀伦，然后較長(zhǎng)的那個(gè)從減掉長(zhǎng)處的那部分開始脆烟，兩個(gè)鏈表同時(shí)遞增，遇到相同的節(jié)點(diǎn)既就是交叉節(jié)點(diǎn)空镜。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int alen = getlen(headA);
int blen = getlen(headB);
if(alen > blen)
return helper(headA,headB,alen-blen);
else
return helper(headB,headA,blen-alen);
}
private ListNode helper(ListNode headA, ListNode headB, int n) {
while(n>0) {
headA = headA.next;
n--;
}
while(headA != headB) {
headA = headA.next;
headB = headB.next;
}
return headA;
}
private int getlen(ListNode head) {
int len=0;
while(head != null) {
len++;
head = head.next;
}
return len;
}
}
第二種解法浩淘，則是利用帶環(huán)鏈表的問題捌朴，我們將第一個(gè)表的尾與第二個(gè)鏈表的頭相連，自然就成了帶環(huán)鏈表张抄，然后的問題就是求出帶環(huán)鏈表的環(huán)起始節(jié)點(diǎn)了砂蔽，這個(gè)可以參考問題帶環(huán)鏈表II.由于題目要求不改變表結(jié)構(gòu)，所以最后恢復(fù)表結(jié)構(gòu)即可署惯。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// get the tail of list A.
ListNode node = headA;
while (node.next != null) {
node = node.next;
}
node.next = headB;
ListNode result = listCycleII(headA);
node.next = null;
return result;
}
private ListNode listCycleII(ListNode head) {
ListNode slow = head, fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
slow = head;
fast = fast.next;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
第三種解法哈希表
先將一個(gè)鏈表存到哈希表中左驾，再遍歷另一個(gè)，找到第一個(gè)存在于哈希表中的節(jié)點(diǎn)就是答案
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
Set<ListNode> setA = new HashSet<>();
while(headA != null) {
setA.add(headA);
headA = headA.next;
}
while(headB != null) {
if(setA.contains(headB))
return headB;
headB = headB.next;
}
return null;
}
