問題很簡單粥诫，兩個無環(huán)的單鏈表有個交點幔荒，找到這個點。不過題目要求不能用額外的空間O(1)啥箭，并且是線型時間O(n)谍珊。
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→c1 → c2 → c3
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.
這個問題我沒有按要求作出來，我只能想到O(n^2)的暴力比較急侥，或者用一個Stack的額外空間O(n)砌滞。于是看看了別人家孩子的代碼炼七。思路非常巧妙，和判斷單鏈表有沒有環(huán)的解法一樣布持，「雙指針同時遍歷兩個鏈表豌拙，到結(jié)尾之后跳到另一個鏈表的頭繼續(xù)遍歷」代碼如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public ListNode getIntersection(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode node1 = headA;
ListNode node2 = headB;
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
if (node1 == node2) return node1; // in case node1 == node2 == null
if (node1 == null) node1 = headB;//這里可能會錯，不要寫成node1=node2
if (node2 == null) node2 = headA;
}
return node1;
}
