写点什么

合并两个单向链表

用户头像
关注
发布于: 2020 年 09 月 20 日

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

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





思路:

长链表向后移动链表长度差值,然后循环比较两个链表的头部指针是否相等,如果相等则返回;不相同,长短链表均向后移动。

时间复杂度:O(max(m,n)),即最长的链表长度

空间复杂度:O(1),未申请新空间

findMergeNode(list1, list2):

int m = list1.length;

int n = list2.lenth;

longLinkedList = m>n?list1:list2;

shortLinkedList = m>n?list2:list2;

int k = Math.abs(m-n);

while(k > 0)

{

longLinkedList = longLinkedList.next;

k--;

}

while(longLinkedList.hasNext())

{

If(longLinkedList == shortLinkedList){

    Return;

}

longLinkedList = longLinkedList.next;

shortLinkedList = shortLinkedList.next;

用户头像

关注

everything will be alright 2020.04.06 加入

还未添加个人简介

评论

发布
暂无评论
合并两个单向链表