单向链表的合并判断及计算

本文是架构师训练营第 8 周课后作业,作业原题为:

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。 

单向链表
单向链表

该问题解决思路如下:

  1. 先计算两个链表的长度 xy,找到较长的那个链表(假设为 longLink);
  2. longLink的头指针向后移动|x-y|个节点,即可保持长、短链表剩下部分长度相等;
  3. 再逐个比较两链表的头指针,如果出现头指针相同的节点则返回该节点,如果不相同则头指针分别向后移动一位;
  4. 循环步骤3,直到两链表遍历结束。

以上过程中,若返回节点为null,则表示两链表未合并;反之,则为合并节点。时间复杂度是O(x+y),即两链表都遍历了。由于没有需要分配额外的空间,空间复杂空为O(1)

上述思路 C# 实现代码如下:

namespace SinglyLinkList 
{  
   public class LinkNode<T> 
   { 
       //数据属性 
       public T Data { get; set; } 
       //指针属性 
       internal LinkNode<T> Next { get; set; } 
       //构造器 
       public LinkNode(T val, LinkNode<T> p) 
       { 
           Data = val; 
           Next = p; 
       } 
       /// <summary> 
       /// 求链表的长度 
       /// </summary> 
       /// <returns></returns> 
       public int GetLength(LinkNode<T> head) 
       { 
           LinkNode<T> pointer = head; 
           int length = 0; 
           while (pointer != null) 
           { 
               pointer = pointer.Next; 
               ++length; 
           } 
           return length; 
       } 
       /// <summary> 
       /// 获取两个链表合并的节点 
       /// </summary> 
       /// <param name="list1">链表1</param> 
       /// <param name="list2">链表2</param> 
       /// <returns></returns> 
       public LinkNode<T> GetMergedNode(LinkNode<T> list1, LinkNode<T> list2) 
       { 
           int x = GetLength(list1); 
           int y = GetLength(list2); 
           var (longLink, shortLink) = x > y ? (list1, list2) : (list2, list1); 
           var delta = Math.Abs(x - y); 
           //移动较长链表 
           do 
           { 
               delta--; 
               longLink = longLink.Next; 
           } 
           while (delta > 0); 
           //寻找相同头指针 
           do 
           { 
               if (longLink == shortLink)  
               { 
                   return longLink; 
               } 
               longLink = longLink.Next; 
               shortLink = shortLink.Next; 
           } 
           while (longLink.Next != null); 
           return null; 
       } 
   } 
}

参考资料:

  1. 单链表及 C# 实现:https://www.jianshu.com/p/9d56373ce68f
  2. 单向链表数据结构:https://www.cnblogs.com/Yellowshorts/p/3522901.html

《单向链表的合并判断及计算》的相关评论

发表评论

必填项已用 * 标记,邮箱地址不会被公开。