第八周课后练习
发布于: 2020 年 11 月 14 日
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用代码（或伪代码）描述算法，并给出时间复杂度。
思路：用两个循环实现，时间复杂度为 Ο(n2)
public class LinkRepeat { public static class ListNode { String value; ListNode next; } /** * @param head1 第一个有序链表 * @param head2 第二个有序链表 * @return */ public static String findRepeat(ListNode head1, ListNode head2) { // 如果第一个链表为空 if (head1 == null) { return null; } // 如果第二个链表为空 if (head2 == null) { return null; } String repeat = ""; while (head1 != null) { ListNode temp=head2; while (temp != null) { if (head1.value.compareTo(temp.value) == 0) { repeat = head1.value; break; } else { temp = temp.next; } } if (!"".equals(repeat)) { break; } else { head1 = head1.next; } } return repeat; } public static void main(String[] args) { ListNode head = new ListNode(); head.value = "a"; head.next = new ListNode(); head.next.value = "b"; head.next.next = new ListNode(); head.next.next.value = "x"; head.next.next.next = new ListNode(); head.next.next.next.value = "y"; head.next.next.next.next = new ListNode(); head.next.next.next.next.value = "z"; ListNode head2 = new ListNode(); head2.value = "d"; head2.next = new ListNode(); head2.next.value = "e"; head2.next.next = new ListNode(); head2.next.next.value = "f"; head2.next.next.next = new ListNode(); head2.next.next.next.value = "x"; head2.next.next.next.next = new ListNode(); head2.next.next.next.next.value = "y"; head2.next.next.next.next.next = new ListNode(); head2.next.next.next.next.next.value = "z"; String repeat = findRepeat(head, head2); System.out.println("链表中重复的元素：" + repeat); }}
划线
评论
复制
发布于: 2020 年 11 月 14 日阅读数: 22
高兵
关注
还未添加个人签名 2018.09.21 加入
还未添加个人简介
评论