1. 题目描述 输入两个链表,找出它们的第一个公共结点。
2. 思路分析 2.1 思路一:栈实现 在第一个公共节点前的节点都是不相同的,因此只要倒序遍历两个链表,找出最后一个出现的相同节点即可。
因为链表不能倒序遍历,所以借助栈实现。
2.2 思路二:快慢指针 假设链表 A 长度大于链表 B 长度,它们的长度差为 diff。
让 A 的指针先移动 diff 的位移,然后 A 和 B 的指针再同时向后移动,每次比较节点,选出第一个出现的相同节点。
3. 代码实现 为了方便,先简单实现节点数据结构:
1 2 3 4 5 6 class Node { constructor (value, next ) { this .value = value this .next = next } }
3.1 思路一:栈实现 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 function method1 (list1, list2 ) { const stack1 = [], stack2 = [] let node = list1 while (node) { stack1.push(node) node = node.next } node = list2 while (node) { stack2.push(node) node = node.next } node = null while (stack1.length && stack2.length) { let top1 = stack1.pop(), top2 = stack2.pop() if (top1 === top2) { node = top1 } else { break } } return node }
3.2 思路二:快慢指针 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 function method2 (list1, list2 ) { let length1 = 0 , length2 = 0 let node = list1 while (node) { ++length1 node = node.next } node = list2 while (node) { ++length2 node = node.next } let diff = Math .abs(length1 - length2), longList = null , shortList = null if (length1 > length2) { longList = list1 shortList = list2 } else { longList = list2 shortList = list1 } while (diff > 0 ) { longList = longList.next --diff } while (longList && shortList) { if (longList === shortList) { return longList } longList = longList.next shortList = shortList.next } return null }
3.3 测试代码 1 2 3 4 5 6 const node4th = new Node(4 )const node3th = new Node(3 , node4th)const list1 = new Node(1 , new Node(2 , new Node(3 , node3th)))const list2 = new Node(5 , new Node(6 , node3th))console .log(method2(list1, list2))