写点什么

架构师训练营第八周作业

用户头像
邓昀垚
关注
发布于: 2020 年 11 月 09 日

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

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

算法思想:

遍历list1,看list1的子链是否是list2的尾链。

算法时间复杂度:

O(n²)

package org.geekbang.week8;
public class CommonLinkedList
{
public static void main(String[] args)
{
Node a = new Node("a");
Node b = new Node("b");
Node d = new Node("d");
Node e = new Node("e");
Node f = new Node("f");
Node x = new Node("x");
Node y = new Node("y");
Node z = new Node("z");
a.next(b);
b.next(x);
x.next(y);
y.next(z);
d.next(e);
e.next(f);
f.next(x);
System.out.println("linkedlist1:");
a.printList();
System.out.println("linkedlist2:");
d.printList();
System.out.println("common list:");
Node commonNode = getCommonNode(a, d);
if (commonNode != null)
{
commonNode.printList();
} else
{
System.out.println("no common node");
}
}
/**
* 判断list2是否是list1的尾链
*
* @param list1
* @param list2
* @return
*/
public static boolean isTail(Node list1, Node list2)
{
if (list1 == null || list2 == null)
{
return false;
}
Node n1 = list1;
Node n2 = list2;
//在list1中找到list2的头结点
while (n1 != n2 && n1 != null)
{
n1 = n1.next();
}
while (n1 != null && n2 != null)
{
if (n1 == n2)
{
n1 = n1.next();
n2 = n2.next();
} else
{
return false;
}
}
//如果是尾链,此时两个指针都应该指向null
if (n1 != null || n2 != null)
{
return false;
} else
{
return true;
}
}
public static Node getCommonNode(Node list1, Node list2)
{
int count1 = list1.count();
int count2 = list2.count();
Node n1 = null;
Node n2 = null;
if (count1 > count2)
{
n1 = list1;
n2 = list2;
} else
{
n1 = list2;
n2 = list1;
}
while (!isTail(n1, n2))
{
n2 = n2.next();
}
return n2;
}
}



package org.geekbang.week8;
public class Node<T>
{
private T data;
private Node<T> next;
public Node(T data)
{
this.data = data;
}
public Node<T> next()
{
return next;
}
public void next(Node<T> next)
{
this.next = next;
}
@Override
public String toString()
{
return data.toString();
}
public void printList()
{
System.out.print(this + " → ");
Node curNode = this;
while (curNode.next != null)
{
curNode = curNode.next;
System.out.print(curNode + " → ");
}
System.out.println("null");
}
public int count()
{
int count = 1;
Node curNode = this;
while (curNode.next != null)
{
count++;
curNode = curNode.next;
}
return count;
}
}



用户头像

邓昀垚

关注

还未添加个人签名 2018.06.04 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第八周作业