第八周作业

用户头像
胡江涛
关注
发布于: 9 小时前
第八周作业
  1. 有两个单向链表(链表长度分别为m,n),这两个单向链表可能在某个元素合并,也可能不合并,如下图所示的这样。

现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?

如果合并,找到合并的元素,也就是图中的x元素。

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



判断是否相交的方法IsIntersect() 和获得向交点GetMeetNode()

IsIntersect()方法

两个没有环的链表如果是相交于某一结点,这个结点后面都是共有的。所以如果两个链表相交,那么两个链表的尾结点的地址也是一样的。程序实现时分别遍历两个单链表,直到尾结点。判断尾结点地址是否相等即可。时间复杂度为O(L1+L2)。

GetMeetNode()方法

先处理长一点的链表,当剩余的节点数与短一点的链表一样长时,再逐个对比。

using System;
namespace ConsoleLinkList
{
class Program
{
static void Main(string[] args)
{
LinkList<string> MyList1 = new LinkList<string>();
MyList1.Add("a");
MyList1.Add("b");
MyList1.Add("x");
MyList1.Add("y");
MyList1.Add("z");
LinkList<string> MyList2 = new LinkList<string>();
MyList2.Add("d");
MyList2.Add("e");
MyList2.Add("f");
MyList2.Add("x");
MyList2.Add("y");
MyList2.Add("z");
bool IsInter = IsIntersect(MyList1.GetNodeByIndex(0), MyList2.GetNodeByIndex(0));
Console.WriteLine("是否相交:" + IsInter);
Node<string> meetNode = GetMeetNode(MyList1.GetNodeByIndex(0), MyList2.GetNodeByIndex(0));
Console.WriteLine("相交节点为:" + meetNode.Data);
Console.ReadKey();
}
/// <summary>
/// 判断是否有交叉
/// 两个没有环的链表如果是相交于某一结点,如图所示,这个结点后面都是共有的。所以如果两个链表相交,那么两个链表的尾结点的地址也是一样的。
/// 程序实现时分别遍历两个单链表,直到尾结点。判断尾结点地址是否相等即可。时间复杂度为O(L1+L2)
/// </summary>
/// <param name="h1"></param>
/// <param name="h2"></param>
/// <returns></returns>
public static bool IsIntersect(Node<string> h1, Node<string> h2)
{
if (h1 == null || h2 == null)
{
return false;
}
Node<string> t1 = h1;
//找链表1的尾结点
while (t1.Next != null)
{
t1 = t1.Next;
}
Node<string> t2 = h2;
//找链表2的尾结点
while (t2.Next != null)
{
t2 = t2.Next;
}
return t1.Data == t2.Data;
}
/// <summary>
/// 获得相交点
/// </summary>
/// <param name="h1"></param>
/// <param name="h2"></param>
/// <returns></returns>
public static Node<string> GetMeetNode(Node<string> h1, Node<string> h2)
{
if (h1 == null || h2 == null)
{
return null;
}
Node<string> t1 = h1;
int len1 = 1;
//找链表1的尾结点
while (t1.Next != null)
{
t1 = t1.Next;
len1++;
}
Node<string> t2 = h2;
int len2 = 1;
//找链表2的尾结点
while (t2.Next != null)
{
t2 = t2.Next;
len2++;
}
//如果不相交
if (t1.Data != t2.Data)
{
return null;
}
Node<string> t_1 = h1;
Node<string> t_2 = h2;
//找出较长的,先遍历
if (len1 > len2)
{
int d = len1 - len2;
while (d != 0)
{
t_1 = t_1.Next;
d--;
}
}
else
{
int d = len2 - len1;
while (d != 0)
{
t_2 = t_2.Next;
d--;
}
}
//同时遍历
while (t_1.Data != t_2.Data)
{
t_1 = t_1.Next;
t_2 = t_2.Next;
}
return t_1;
}
/// <summary>
/// 链表
/// </summary>
/// <typeparam name="T"></typeparam>
public class LinkList<T>
{
private Node<T> head;//存储一个头结点
public LinkList()
{
head = null;
}
/// <summary>
/// 获取链表长度
/// </summary>
/// <returns></returns>
public int GetLength()
{
if (head == null) return 0;
Node<T> temp = head;
int count = 1;
while (true)
{
if (temp.Next != null)
{
count++;
temp = temp.Next;
}
else
{
break;
}
}
return count;
}
/// <summary>
/// 清除链表
/// </summary>
public void Clear()
{
head = null;
}
/// <summary>
/// 判断链表是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return head == null;
}
/// <summary>
/// 给链接添加新节点
/// </summary>
/// <param name="item"></param>
public void Add(T item)
{
Node<T> newNode = new Node<T>(item);//根据新的数据创建一个新的节点
//如果头结点为空,那么这个新的节点就是头节点
if (head == null)
{
head = newNode;
}
else
{
//把新来的结点放到 链表的尾部
//要访问到链表的尾结点
Node<T> temp = head;
while (true)
{
if (temp.Next != null)
{
temp = temp.Next;
}
else
{
break;
}
}
temp.Next = newNode;//把新来的结点放到 链表的尾部
}
}
/// <summary>
/// 给链接插入一个节点
/// </summary>
/// <param name="item"></param>
/// <param name="index"></param>
public void Insert(T item, int index)
{
Node<T> newNode = new Node<T>(item);
if (index == 0) //插入到头节点
{
newNode.Next = head;
head = newNode;
}
else
{
Node<T> temp = head;
for (int i = 1; i <= index - 1; i++)
{
//让temp向后移动一个位置
temp = temp.Next;
}
Node<T> preNode = temp;
Node<T> currentNode = temp.Next;
preNode.Next = newNode;
newNode.Next = currentNode;
}
}
/// <summary>
/// 删除链表的一个节点
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T Delete(int index)
{
T data = default(T);
if (index == 0) //删除头结点
{
data = head.Data;
head = head.Next;
}
else
{
Node<T> temp = head;
for (int i = 1; i <= index - 1; i++)
{
//让temp向后移动一个位置
temp = temp.Next;
}
Node<T> preNode = temp;
Node<T> currentNode = temp.Next;
data = currentNode.Data;
Node<T> nextNode = temp.Next.Next;
preNode.Next = nextNode;
}
return data;
}
/// <summary>
/// 获取此链表某一个索引的节点的Data
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
Node<T> temp = head;
for (int i = 1; i <= index; i++)
{
//让temp向后移动一个位置
temp = temp.Next;
}
return temp.Data;
}
}
/// <summary>
/// 获取此链表某一个索引的节点的Data
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T GetElement(int index)
{
return this[index];
}
/// <summary>
/// 获取value数据对应的此链表的索引
/// </summary>
/// <param name="value"></param>
/// <returns></returns>
public int Locate(T value)
{
Node<T> temp = head;
if (temp == null)
{
return -1;
}
else
{
int index = 0;
while (true)
{
if (temp.Data.Equals(value))
{
return index;
}
else
{
if (temp.Next != null)
{
temp = temp.Next;
}
else
{
break;
}
}
}
return -1;
}
}
/// <summary>
/// 根据索引获取节点
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public Node<T> GetNodeByIndex(int i)
{
if (i < 0 || i > this.GetLength() - 1)
{
return null;
}
Node<T> currNode = head;
for (int m = 0; m < this.GetLength(); m++, currNode = currNode.Next)
{
if (m == i)
{
return currNode;
}
}
return null;
}
}
/// <summary>
/// 单链表的结点
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T>
{
private T data;//存储数据
private Node<T> next;//指针 用来指向下一个元素
#region 多种构造函数
public Node()
{
data = default(T);
next = null;
}
public Node(T value)
{
data = value;
next = null;
}
public Node(Node<T> next)
{
this.next = next;
}
public Node(T value, Node<T> next)
{
this.data = value;
this.next = next;
}
#endregion
/// <summary>
/// 存储的数据
/// </summary>
public T Data
{
get { return data; }
set { data = value; }
}
/// <summary>
/// 指向下一个Node
/// </summary>
public Node<T> Next
{
get { return next; }
set { next = value; }
}
}
}
}

Note:

链表

链表可以使用零散的内存空间存储数据。所以,链表中的每个数据都必须包含一个指向下一个数据元素的内存指针。想要在链表中查找一个数据,只能遍历链表,所以链表的查找复杂度是O(N).





用户头像

胡江涛

关注

放肆才叫青春 2019.05.11 加入

IT软件工程师,一枚

评论

发布
暂无评论
第八周作业