图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点

[sisterAn]

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

 

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null.
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

附leetcode地址：leetcode

[hh-cheng]

方法：遍历

• 先将两个链表转换成数组结构
• 对其中一个数组进行遍历，每次遍历判断另一个数组是否含有该值
• 遍历结束后如果没有找到就返回 null

function intersectNode( head1, head2 ) {
 var arr1 = [],
 arr2 = [],
 theValue = null;
 transformToArray( head1, arr1 );
 transformToArray( head2, arr2 );

 for (var i = 0; i < arr1.length; i++) {
 if( arr2.indexOf(arr1[i]) !== -1 ){
 theValue = arr1[i];
 return 'Reference of the node with value = ' + theValue;
 }
 }
 return theValue;

 /*
 arr1.some( value => {
 if ( arr2.includes(value) ){
 theValue = value;
 return true;
 }
 })
 if( theValue ){
 return 'Reference of the node with value = ' + theValue;
 } 
 return null;
 */
}

function transformToArray( head, arr ) {
 while( head ){
 arr.push(head.val);
 head = head.next;
 }
}

---

测试代码：

function CreateNode(val){
 this.val = val;
 this.next = null;
}
function CreateList(...nodes){
 this.head = nodes[0];
 this.length = nodes.length;
 for( var i = 0; i < nodes.length - 1; i++ ){
 if( nodes[i+1] ){
 nodes[i].next = nodes[i+1];
 }
 }
}

function intersectNode( head1, head2 ) {
 var arr1 = [],
 arr2 = [],
 theValue = null;
 transformToArray( head1, arr1 );
 transformToArray( head2, arr2 );

 for (var i = 0; i < arr1.length; i++) {
 if( arr2.indexOf(arr1[i]) !== -1 ){
 theValue = arr1[i];
 return 'Reference of the node with value = ' + theValue;
 }
 }
 return theValue;
}
function transformToArray( head, arr ) {
 while( head ){
 arr.push(head.val);
 head = head.next;
 }
}

const node1 = new CreateNode(1);
const node2 = new CreateNode(2);
const node3 = new CreateNode(3);
const node4 = new CreateNode(4);
const node5 = new CreateNode(5);
const nodeA = new CreateNode('A');
const nodeB = new CreateNode('B');
const nodeC = new CreateNode('C');
const nodeD = new CreateNode('D');
const nodeE = new CreateNode('E');
const list1 = new CreateList(node1, node2, node3, node4, node5);
const list2 = new CreateList(nodeA, nodeB, node3, nodeC, nodeD);

intersectNode(list1.head, list2.head);

[hecun0000]

1. 将一个链表的值放入 map, 遍历另一个链表，判断有无该节点

var getIntersectionNode = function (headA, headB) {
 var map = new WeakMap()
 while (headA) {
 map.set(headA, true)
 headA = headA.next
 }
 while (headB) {
 var curr = map.get(headB)
 if (curr) return headB
 headB = headB.next
 }
 return null
};

[sisterAn]

解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)

解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。

若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null

const getIntersectionNode = function(headA, headB) {
 while(headA) {
 headA.flag = true
 headA = headA.next
 }
 while(headB) {
 if (headB.flag) return headB
 headB = headB.next
 }
 return null
};

时间复杂度：O(n)

空间复杂度：O(n)

解法二：双指针法

解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。

我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。

解题步骤：

• 同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设A为长链表
• 那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
• 此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
• 此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

画图帮助理解：

const getIntersectionNode = function(headA, headB) {
 // 清除高度差
 let pA = headA, pB = headB
 while(pA || pB) {
 if(pA === pB) return pA
 pA = pA === null ? headB : pA.next
 pB = pB === null ? headA : pB.next
 }
 return null
};

时间复杂度：O(n)

空间复杂度：O(1)

leetcode

[sisterAn]

方法：遍历

• 先将两个链表转换成数组结构
• 对其中一个数组进行遍历，每次遍历判断另一个数组是否含有该值
• 遍历结束后如果没有找到就返回 null

function intersectNode( head1, head2 ) {
 var arr1 = [],
 arr2 = [],
 theValue = null;
 transformToArray( head1, arr1 );
 transformToArray( head2, arr2 );

 for (var i = 0; i < arr1.length; i++) {
 if( arr2.indexOf(arr1[i]) !== -1 ){
 theValue = arr1[i];
 return 'Reference of the node with value = ' + theValue;
 }
 }
 return theValue;

 /*
 arr1.some( value => {
 if ( arr2.includes(value) ){
 theValue = value;
 return true;
 }
 })
 if( theValue ){
 return 'Reference of the node with value = ' + theValue;
 } 
 return null;
 */
}

function transformToArray( head, arr ) {
 while( head ){
 arr.push(head.val);
 head = head.next;
 }
}

测试代码：

function CreateNode(val){
 this.val = val;
 this.next = null;
}
function CreateList(...nodes){
 this.head = nodes[0];
 this.length = nodes.length;
 for( var i = 0; i < nodes.length - 1; i++ ){
 if( nodes[i+1] ){
 nodes[i].next = nodes[i+1];
 }
 }
}

function intersectNode( head1, head2 ) {
 var arr1 = [],
 arr2 = [],
 theValue = null;
 transformToArray( head1, arr1 );
 transformToArray( head2, arr2 );

 for (var i = 0; i < arr1.length; i++) {
 if( arr2.indexOf(arr1[i]) !== -1 ){
 theValue = arr1[i];
 return 'Reference of the node with value = ' + theValue;
 }
 }
 return theValue;
}
function transformToArray( head, arr ) {
 while( head ){
 arr.push(head.val);
 head = head.next;
 }
}

const node1 = new CreateNode(1);
const node2 = new CreateNode(2);
const node3 = new CreateNode(3);
const node4 = new CreateNode(4);
const node5 = new CreateNode(5);
const nodeA = new CreateNode('A');
const nodeB = new CreateNode('B');
const nodeC = new CreateNode('C');
const nodeD = new CreateNode('D');
const nodeE = new CreateNode('E');
const list1 = new CreateList(node1, node2, node3, node4, node5);
const list2 = new CreateList(nodeA, nodeB, node3, nodeC, nodeD);

intersectNode(list1.head, list2.head);

想法不错，不过可以进阶一下，使用双指针来做，使之尽量满足空间复杂度O(1)

[cs739295]

方法：遍历

• 先将两个链表转换成数组结构
• 对其中一个数组进行遍历，每次遍历判断另一个数组是否含有该值
• 遍历结束后如果没有找到就返回 null

function intersectNode( head1, head2 ) {
 var arr1 = [],
 arr2 = [],
 theValue = null;
 transformToArray( head1, arr1 );
 transformToArray( head2, arr2 );

 for (var i = 0; i < arr1.length; i++) {
 if( arr2.indexOf(arr1[i]) !== -1 ){
 theValue = arr1[i];
 return 'Reference of the node with value = ' + theValue;
 }
 }
 return theValue;

 /*
 arr1.some( value => {
 if ( arr2.includes(value) ){
 theValue = value;
 return true;
 }
 })
 if( theValue ){
 return 'Reference of the node with value = ' + theValue;
 } 
 return null;
 */
}

function transformToArray( head, arr ) {
 while( head ){
 arr.push(head.val);
 head = head.next;
 }
}

测试代码：

function CreateNode(val){
 this.val = val;
 this.next = null;
}
function CreateList(...nodes){
 this.head = nodes[0];
 this.length = nodes.length;
 for( var i = 0; i < nodes.length - 1; i++ ){
 if( nodes[i+1] ){
 nodes[i].next = nodes[i+1];
 }
 }
}

function intersectNode( head1, head2 ) {
 var arr1 = [],
 arr2 = [],
 theValue = null;
 transformToArray( head1, arr1 );
 transformToArray( head2, arr2 );

 for (var i = 0; i < arr1.length; i++) {
 if( arr2.indexOf(arr1[i]) !== -1 ){
 theValue = arr1[i];
 return 'Reference of the node with value = ' + theValue;
 }
 }
 return theValue;
}
function transformToArray( head, arr ) {
 while( head ){
 arr.push(head.val);
 head = head.next;
 }
}

const node1 = new CreateNode(1);
const node2 = new CreateNode(2);
const node3 = new CreateNode(3);
const node4 = new CreateNode(4);
const node5 = new CreateNode(5);
const nodeA = new CreateNode('A');
const nodeB = new CreateNode('B');
const nodeC = new CreateNode('C');
const nodeD = new CreateNode('D');
const nodeE = new CreateNode('E');
const list1 = new CreateList(node1, node2, node3, node4, node5);
const list2 = new CreateList(nodeA, nodeB, node3, nodeC, nodeD);

intersectNode(list1.head, list2.head);

想法不错，不过可以进阶一下，使用双指针来做，使之尽量满足空间复杂度O(1)

解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)

解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。

若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null

var getIntersectionNode = function(headA, headB) {
 while(headA) {
 headA.flag = true
 headA = headA.next
 }
 while(headB) {
 if (headB.flag) return headB
 headB = headB.next
 }
 return null
};

时间复杂度：O(n)

空间复杂度：O(n)

解法二：双指针法

解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。

我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。

解题步骤：

• 同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设A为长链表
• 那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
• 此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
• 此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

画图帮助理解：

var getIntersectionNode = function(headA, headB) {
 // 清除高度差
 let pA = headA, pB = headB
 while(pA || pB) {
 if(pA === pB) return pA
 pA = pA === null ? headB : pA.next
 pB = pB === null ? headA : pB.next
 }
 return null
};

时间复杂度：O(n)

空间复杂度：O(1)

leetcode

你好，我想问一下，if(pA === pB) return pA。这行代码怎么理解？题目表示是两个单独的链表，链表里的节点都是对象，对象的这种===会有效吗？他们两个好像是指向不同的地址空间把。是不是应该比较pA与pB的值才行。改为if(pA.val===pB) return pA;会不会更好一点？

[Been101]

const getIntersectionNode = (head1, head2) => {
 const h1 = head1
 const h2 = head2
 while (h1 || h2) {
 if(h1.data === h2.data) return h1
 h1 = h1 === null ? head2 : h1.next
 h2 = h2 === null ? head1 : h2.next
 }
 return null
 } 

[AnranS]

WeakMap

var getIntersectionNode = function (headA, headB) {
 let currenA = headA, currenB = headB;
 let map = new WeakMap();
 while(currenA) {
 map.set(currenA, true);
 currenA = currenA.next;
 }

 while(currenB) {
 if(map.has(currenB)) return currenB.val;
 currenB = currenB.next;
 }
 return null;
};

双指针

var getIntersectionNode = function (headA, headB) {
 let currentA = headA, currentB = headB;
 while(currentA || currentB) {
 if(currentB === currentA) return currentA;
 currentA = currentA === null ? headB : currentA.next; 
 currentB = currentB === null ? headA : currentB.next; 
 }
 return null;
};

[xiaoerwen]

const getIntersectionNode = (headA, headB) => {
 if (!headA || !headB) {
 return null;
 }

 let tailA = headA;
 let tailB = headB;
 let stackA = [];
 let stackB = [];
 // 获取链表A的尾结点
 while (tailA.next) {
 stackA.push(tailA);
 tailA = tailA.next;
 }
 // 获取链表B的尾结点
 while (tailB.next) {
 stackB.push(tailB);
 tailB = tailB.next;
 }

 let count = 1;
 while (stackA.length && stackB.length) {
 // 如果尾结点相等，往前移动指针
 if (tailA === tailB) {
 tailA = stackA.pop();
 tailB = stackB.pop();
 count++;
 }
 // 否则代表到了不相交初了，终止遍历
 else {
 break;
 }
 }

 /**
 * count为1有两种情况
 * 第一种：链表A和链表B都只有一个节点，那么判断他们是否相等即可
 * 第二种：遍历俩链表都没有相等的节点，证明俩链表不相交，返回null
 */
 if (count === 1) {
 return tailA === tailB ? tailA : null;
 }

 /**
 * 同理存在两种情况
 * 第一种：遍历完俩链表，每个节点都相等，那么返回头节点
 * 第二种：在不相交的节点处循环中断了，相交节点应该等于当前节点的下一个节点
 */
 return tailA === tailB ? tailA : tailA.next;
};

[JohnApache]

解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)

解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。

若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null

const getIntersectionNode = function(headA, headB) {
 while(headA) {
 headA.flag = true
 headA = headA.next
 }
 while(headB) {
 if (headB.flag) return headB
 headB = headB.next
 }
 return null
};

时间复杂度：O(n)

空间复杂度：O(n)

解法二：双指针法

解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。

我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。

解题步骤：

• 同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设A为长链表
• 那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
• 此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
• 此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

画图帮助理解：

const getIntersectionNode = function(headA, headB) {
 // 清除高度差
 let pA = headA, pB = headB
 while(pA || pB) {
 if(pA === pB) return pA
 pA = pA === null ? headB : pA.next
 pB = pB === null ? headA : pB.next
 }
 return null
};

时间复杂度：O(n)

空间复杂度：O(1)

leetcode

我觉得 双指针消除高度差的方案， 时间复杂度并不是 On , 在 极限差的情况下 [4,1,8,4,5] , [5,0,1,8,4,5]，假如相交的节点是最后一个点，会出现 遍历两遍链表的情况, 。

我自己实现了的方案，也是 双指针，但是最多只会遍历一次，不会出现遍历两遍的情况，

class Node {
 public next: Node | undefined;
 constructor (public element: any) {}
}
const getInsersectionNode = (headA: Node, headB: Node) => {
 const map = new Map();
 if (headA === headB) return headA;
 let nextA: Node | undefined = headA;
 let nextB: Node | undefined = headB;
 while (nextA || nextB) {
 if (map.get(nextA)) return nextA;
 if (map.get(nextB)) return nextB;
 if (nextA) {
 map.set(nextA, true);
 nextA = nextA.next;
 }
 if (nextB) {
 map.set(nextB, true);
 nextB = nextB.next;
 }
 }
 return undefined;
};