原题链接在这里：

题目：

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.

题解：

找到length diff, 长的list head先移动diff次, 再一起移动找相同点.

Time Complexity: O(len1 + len2), len1 is the length of list one. len2 is the length of list two.

Space: O(1).

AC Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {14         int len1 = length(headA);15         int len2 = length(headB);16         while(len1 > len2){17             headA = headA.next;18             len1--;19         }20         21         while(len2 > len1){22             headB =headB.next;23             len2--;24         }25         26         while(headA != headB){27             headA = headA.next;28             headB = headB.next;29         }30         31         return headA;32     }33     34     private int length(ListNode head){35         int len = 0;36         while(head != null){37             head = head.next;38             len++;39         }40         return len;41     }42 }

有一巧妙地方法来综合掉 length diff, a = headA, b = headB, a和b一起移动。当a到了list A的末位就跳到HeadB, b到了List B的末位就跳到HeadA.

等a和b相遇就是first intersection node. 因为a把first intersection node之前的list A部分, list B部分都走了一次. b也是如此. diff就综合掉了.

若是没有intersection, 那么a走到list B的结尾 null时, b正好走到 list A的结尾null, a==b. 返回了null.

Time Complexity: O(len1 + len2), len1 is the length of list one. len2 is the length of list two.

Space: O(1).

AC  Java:

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {14         ListNode a = headA;15         ListNode b = headB;16         while(a != b){17             a = a==null ? headB : a.next;18             b = b==null ? headA : b.next;19         }20         return a;21     }22 }