找出两个链表中合并的元素
发布于: 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 年 11 月 16 日阅读数: 30
晨
关注
还未添加个人签名 2020.05.01 加入
还未添加个人简介
评论