写点什么

找出两个链表中合并的元素

用户头像
关注
发布于: 2020 年 11 月 16 日

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用代码(或伪代码)描述算法,并给出时间复杂度。


算法复杂度 O(m + n)

function ListNode(val) {    this.val = val    this.next = null}
/** * @param {Integer[]} arr * @return {ListNode} */function createList(arr) { if (arr.length === 0) { return null } let root = new ListNode(arr[0]) let curtNode = root for (let i = 1; i < arr.length; i++) { let nextNode = new ListNode(arr[i]) curtNode.next = nextNode curtNode = nextNode } return root}
/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */function getListLength(node) { let len = 0 let curtNode = node while (curtNode) { curtNode = curtNode.next len += 1 } return len}
function getIntersectionNode(headA, headB) { // Get list A and list B length: m, n let m = getListLength(headA) let n = getListLength(headB) let nodeA = headA let nodeB = headB // Have two pointers: p1 for A, p2 for B // - if m >= n: p1 = m - n, p2 = 0 // - else: p1 = 0, p2 = n - m if (m >= n) { for (let i = 0; i < m - n; i++) { nodeA = nodeA.next } } else { for (let i = 0; i < n - m; i++) { nodeB = nodeB.next } } // Increment p1 and p2 in the same time and compare, exit when node(p1).val === node(p2).val while (nodeA) { if (nodeA.val === nodeB.val) { return nodeA } nodeA = nodeA.next nodeB = nodeB.next } return null}
function test1() { let headA = createList([4, 1, 8, 4, 5]) let headB = createList([7, 10, 5, 6, 11, 8, 4, 5]) console.log(getListLength(headA)) console.log(getListLength(headB)) let node = getIntersectionNode(headA, headB) console.log(node.val)}
test1()
复制代码


用户头像

关注

还未添加个人签名 2020.05.01 加入

还未添加个人简介

评论

发布
暂无评论
找出两个链表中合并的元素