第八周作业

关注
发布于: 2020 年 07 月 26 日
有两个单向链表（链表长度分别为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).
﻿
﻿
发布于: 2020 年 07 月 26 日阅读数: 51
胡江涛

关注
放肆才叫青春 2019.05.11 加入
IT软件工程师，一枚
发布
暂无评论
创作场景

第八周作业

胡江涛

评论
