[Algorithm] Find merge point of two linked list
List of Find Merge ALGORITHM two point Linked
2023-09-14 08:59:14 时间
Assume we have two linked list, we want to find a point in each list, from which all the the nodes share the same value in both list. Then we call this point is "merge point".
In the iamge, the merge point shoud be Node(7).
// Link A length 4, Link B length 5
// All the node after the merge point should be the same
// based on that, we can make sure that the merge point should
// happens in range [x, c] or [y, c], it is not possible to happen at z
// A x - x - c - c
// B z - y - y - c - c
function Node(val) { return { val, next: null }; } function Link() { return { head: null, tail: null, length: 0, add(val) { const newNode = new Node(val); if (this.length === 0) { this.head = newNode; this.tail = newNode; this.tail.next = null; } else { let temp = this.tail; this.tail = newNode; temp.next = this.tail; } this.length++; } }; } // O ( m + n ), Space: O(1) function findMergePoint(a, b) { // Link A length 4, Link B length 5 // All the node after the merge point should be the same // based on that, we can make sure that the merge point should // happens in range [x, c] or [y, c], it is not possible to happen at z // A x - x - c - c // B z - y - y - c - c let diff, headA = a.head, headB = b.head; if (a.length > b.length) { // O(1) diff = a.length - b.length; [a, b] = [b, a]; } else { diff = b.length - a.length; } // reach +diff step for longer for (let i = 0; i < diff; i++) { headB = headB.next; // O(m) } while (headA != null && headB.val != null ) { // O(n) if (headA.val === headB.val) { return headA; } headA = headA.next; headB = headB.next; } return null; } const lA = new Link(); lA.add(4); lA.add(6); lA.add(7); lA.add(1); const lB = new Link(); lB.add(9); lB.add(3); lB.add(5); lB.add(7); lB.add(1); console.log(findMergePoint(lA, lB)); // Object {val: 7, next: Object}
相关文章
- 老程序员Java数组转List都这样操作「建议收藏」
- 详解List的toArray()方法和toArray(T[] a)方法
- java集合中:set与list相互转换[通俗易懂]
- java list 转json 字符串_Java之JSON字符串与List集合之间相互转换
- 【C++】STL 模拟实现之 list
- ORA-30513: cannot create system triggers of INSTEAD OF type ORACLE 报错 故障修复 远程处理
- ORA-32038: number of WITH clause column names does not match number of elements in select list ORACLE 报错 故障修复 远程处理
- ORA-32485: element in cycle column list of CYCLE clause must appear in the column alias list of the WITH clause element ORACLE 报错 故障修复 远程处理
- ORA-32489: element in sort specification list of SEARCH clause did not appear in the column alias list of the WITH clause element ORACLE 报错 故障修复 远程处理
- ORA-38441: System could not derive the list of STORED and INDEXED attributes. ORACLE 报错 故障修复 远程处理
- ORA-55329: same model string specified more than once in the list of models ORACLE 报错 故障修复 远程处理
- ORA-09320: szrfc: unable to obtain the list of valid OS roles ORACLE 报错 故障修复 远程处理
- ORA-14309: Total count of list values exceeds maximum allowed ORACLE 报错 故障修复 远程处理
- Python list列表详解
- 实现java 中 list集合中有几十万条数据,每100条为一组取出详解编程语言
- java集合框架之List接口详解编程语言
- SAP报表中TOP_OF_PAGE 和END_OF_LIST的使用详解编程语言
- 类型探索Redis中List数据结构的优势(redis中的list)
- 使用Redis实现List存储(向redis中存list)
- 使用Redis集合和List实现高效存储(redis集合和list)
- 警惕Redis List被空出(redis里list为空)
- 使用Redis轻松获取List元素(redis 返回list)
- 跟老齐学Python之list和str比较