写点什么

第 8 周作业

用户头像
hunk
关注
发布于: 2020 年 12 月 13 日
作业一:

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

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



解题思路:

如果两个链表能够合并,说明从某一位置开始,两者尾部的节点完全相同;

1、把较长列表的指针移动到与较短链表相同的位置;

2、开始比较较短的链表的头指针与较长的链表当前指针的值大小;

3、如果相等,则递归判断后续两者的所有节点;

4、如果不相等,则两个链表的指针向后移动。



算法时间复杂度:

O(log(min(m,n)));

实现代码:
package demo.linkedlist;
/**
* 链表结构
*/
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class JudgeLinkedListMerge {
// 判断两个链表是否能够合并返回合并的元素
public ListNode judgeLinkedListMerge(ListNode nodeM,ListNode nodeN ,int m, int n) {
ListNode shorterNode = null;
ListNode longerNode = null;
if(m>n) {
longerNode = nodeM;
shorterNode = nodeN;
} else {
longerNode = nodeN;
shorterNode = nodeM;
}
// 如果能够合并,那么一定是较短的链表中某个元素之后与较长链表完全相同
// 计算链表长度差值
int diff = Math.abs(m-n);
// 使较长的链表直接达到diff长度位置再开始比较。
while(diff>0) {
longerNode = longerNode.next;
diff--;
}
// 开始判断较短链表的某一个是否能够与较长节点的当前节点是否相同
while(shorterNode != null) {
if(shorterNode.val == longerNode.val) {
// 递归判断两者的尾部节点是否都相等
if(judgeLinkedListMerge(shorterNode.next,longerNode.next)) {
return shorterNode;
}
} else {
// 两个链表的指针向后移动
shorterNode = shorterNode.next;
longerNode = longerNode.next;
}
}
return null;
}
/**
* 节点是否相同
* @param nodeM
* @param nodeN
* @return
*/
public boolean judgeRecursion(ListNode nodeM,ListNode nodeN) {
if(nodeM!=null && nodeN!=null) {
if(nodeM.val == nodeN.val) {
// 判断下一层
return judgeLinkedListMerge(nodeM.next,nodeN.next);
} else {
return false;
}
} else {
// 如果直到结束都相同,那么返回true
return true;
}
}
}



发布于: 2020 年 12 月 13 日阅读数: 19
用户头像

hunk

关注

还未添加个人签名 2019.01.23 加入

还未添加个人简介

评论

发布
暂无评论
第8周作业