题目:编写一个程序,找到两个单链表相交的起始节点。
注意:
- 如果两个链表没有交点,返回 null.
- 在返回结果后,两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
代码:
1 /** 2 * Definition for singly-linked list. 3 * function ListNode(val) { 4 * this.val = val; 5 * this.next = null; 6 * } 7 */ 8 9 /** 10 * @param {ListNode} headA 11 * @param {ListNode} headB 12 * @return {ListNode} 13 */ 14 var getIntersectionNode = function(headA, headB) { 15 let n1 = headA 16 let n2 = headB 17 while(n1!=n2){ 18 if(n1 === null ){ 19 n1 = headB 20 }else{ 21 n1 = n1.next 22 } 23 if(n2 === null ){ 24 n2 = headA 25 }else{ 26 n2 = n2.next 27 } 28 } 29 return n1 30 };