Week 08- 作业一：双链表公共节点

关注

发布于: 2020 年 07 月 28 日

双链表有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
实现：c# net core
节点定义：
 public class ListNode<T>
    {
        public T Val;
        public ListNode<T> Next;
        public ListNode(T x) { Val = x; }
    }
﻿
思路一，遍历2个链表，并使用HASH存储，依赖HASH的特性来寻找第一个公共节点
﻿
 public ListNode<T> FindMergeNodeHash<T>(ListNode<T> head1, ListNode<T> head2)
        {
            ListNode<T> current1 = head1;
            ListNode<T> repeat = head2;
            HashSet<ListNode<T>> tt = new HashSet<ListNode<T>>();
            tt.Add(current1);
            while (current1.Next != null)
            {
                tt.Add(current1.Next);
                current1 = current1.Next;
            }
            current1 = head2;
            while (current1.Next != null)
            {
                if (tt.Contains(current1.Next))
                {
                    repeat = current1.Next;
                    break;
                }
                current1 = current1.Next;
            }
            return repeat;
        }
时间复杂度：O(m+n)
空间复杂度：O(m+n)
﻿
思路二  需要修改链表
将第一条链表NEXT全部置为NULL,然后遍历第二个链表，第一个NEXT为NULL的NODE，即为公共节点
public ListNode<T> FindMergeNodeHash2<T>(ListNode<T> head1, ListNode<T> head2)
{
    ListNode<T> current1 = head1;
    while (head1.Next != null)
    {
        current1 = head1;
        head1 = head1.Next;
        current1.Next = null;
    }
    while (head2.Next != null)
    {
        head2 = head2.Next;
    }
    return head2;
}
时间复杂度：O(m+n)
空间复杂度：O(1)
﻿
思路三  双指针法，这个是看网上题解得到的
两个链表长度分别为L1+C、L2+C， C为公共部分的长度， 第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个链表到达公共节点
 ListNode node1 = headA;
 ListNode node2 = headB;        
 while (node1 != node2) {
     node1 = node1 != NULL ? node1->next : headB;
     node2 = node2 != NULL ? node2->next : headA;
 }
 return node1;
时间复杂度：O(m+n)
空间复杂度：O(1)
﻿
DataNode 服务器节点宕机的时候，HDFS 的处理过程时序图
﻿