检查两个链接列表是否合并。如果是,在哪里?

如果

• “不允许修改”的意思是“您可以更改,但最终应恢复”,以及
• 我们可以迭代列表 两次

下面的算法就是解决方案。

首先是数字。假设第一个列表是长度 a+c 第二个是长度 b+c ,在哪里 c 是它们共同的“尾巴”的长度(在合并点之后)。让我们把它们表示为:

x = a+c
y = b+c

因为我们不知道长度,我们会计算 x 和 y 如果没有额外的迭代,您将看到如何进行。

然后,我们迭代每个列表,并在迭代时反转它们!如果两个迭代器同时到达合并点,那么我们仅通过比较就可以找到它。否则,一个指针将先于另一个指针到达合并点。

之后,当另一个迭代器到达合并点时,它将不会继续到公共尾部。相反,将返回到以前到达合并点的列表的前一个开头!因此,在它到达更改列表的末尾(即另一个列表的前一个开头)之前,他将 a+b+1 迭代总数。让我们称之为 z+1 .

首先到达合并点的指针将继续迭代,直到到达列表的末尾。它所做的迭代次数应该计算并等于 X .

然后,这个指针返回并再次反转列表。但现在它不会回到它最初开始的列表的开头!相反,它将转到另一个列表的开头!它所做的迭代次数应计算并等于 是 .

所以我们知道以下数字:

x = a+c
y = b+c
z = a+b

从中我们可以确定

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

这就解决了问题。

以下是迄今为止我所看到的最伟大的——O(N),没有计数器。我是在一次S.N.的面试中得到的。 VisionMap .

像这样做一个交互指针:它每次向前移动到末尾,然后跳到相反列表的开头,依此类推。 创建其中两个,指向两个头部。 每次向前移动1个指针,直到它们相遇。 这将在一次或两次通过后发生。

我在采访中仍然会用到这个问题,但是要想知道为什么这个解决方案有效需要多长时间。

Pavel的答案需要修改列表 以及 对每个列表进行两次迭代。

这里有一个解决方案 只有 需要对每个列表进行两次迭代(第一次是计算它们的长度;如果给定了长度,则只需迭代一次)。

其思想是忽略较长列表的起始项(合并点不能在那里),以便两个指针与列表的结尾距离相等。然后向前移动它们直到它们合并。

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

这与我的另一个答案是渐进的(线性时间),但可能有较小的常数,所以可能更快。但我觉得我的另一个答案更酷。

好吧,如果你知道他们会合并:

假设你从以下开始:

A-->B-->C
        |
        V
1-->2-->3-->4-->5

1)遍历第一个列表,将下一个指针设置为空。

现在你有:

A   B   C

1-->2-->3   4   5

2)现在浏览第二个列表,直到看到一个空值,即合并点。

如果您不能确定它们是否合并,您可以使用一个sentinel值作为指针值,但这并没有那么优雅。

如果我们可以重复列表两次,那么我可以提供确定合并点的方法:

• 迭代两个列表并计算长度a和b
• 计算长度差c=a-b
• 同时开始迭代这两个列表,但在列表上执行更多的C步骤
• 这两个指针将在合并点中相遇。

这里有一个解决方案,计算速度很快(迭代每个列表一次),但使用了大量内存:

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item

这可能违反了“仅解析每个列表一次”条件,但实现了 tortoise and hare algorithm (用于查找循环列表的合并点和循环长度)因此从列表A开始,当您在末尾达到空值时,您假装它是指向列表B开头的指针,从而创建循环列表的外观。然后,该算法将告诉您合并列表到底有多远(根据维基百科的描述,变量“mu”)。

另外,“lambda”值告诉您列表B的长度,如果您愿意,可以在算法期间计算出列表A的长度(当您重定向空链接时)。

可以使用一组节点。遍历一个列表并将每个节点添加到集合中。然后遍历第二个列表,对于每个迭代,检查节点是否存在于集合中。如果是这样,您就找到了合并点:)

也许我过度简化了这个,但是只需迭代最小的列表并使用最后的节点 Link 作为合并点?

所以,在哪里 Data->Link->Link == NULL 是终点,给予 Data->Link 作为合并点(在列表的末尾)。

编辑:

好的,从你发布的图片中,你分析两个列表,最小的第一个。使用最小的列表,您可以维护对以下节点的引用。现在,当您分析第二个列表时,您将对引用进行比较,以找到引用[i]在LinkedList[i]->Link处的引用位置。这将给出合并点。用图片解释的时间(将值叠加在图片上操作)。

您有一个链接列表(参考如下所示):

A->B->C->D->E

您有第二个链接列表:

1->2->

对于合并的列表,引用将如下所示:

1->2->D->E->

因此,您映射第一个“较小的”列表(作为合并列表,我们正在计算的是长度为4,主列表5)

循环浏览第一个列表,维护引用的引用。

该列表将包含以下引用 Pointers { 1, 2, D, E } .

现在我们来看看第二个列表:

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

当然,您维护了一个新的指针列表,但这并不超出规范。但是,第一个列表只解析一次,并且只有在没有合并点的情况下,第二个列表才会被完全解析。否则,它将很快结束(在合并点)。

我在fc9 x86_64上测试了一个合并案例,并按如下所示打印每个节点地址:

Head A 0x7fffb2f3c4b0
0x214f010
0x214f030
0x214f050
0x214f070
0x214f090
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170


Head B 0x7fffb2f3c4a0
0x214f0b0
0x214f0d0
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170

注意,因为我已经对齐了节点结构,所以当malloc()一个节点时,地址与16字节对齐,请参见至少4位。 最小位为0,即0x0或000B。 因此,如果您也处于相同的特殊情况(对齐的节点地址),那么您可以使用这至少4位。 例如,当两个列表都从头到尾移动时,设置访问节点地址的4位中的1或2,即设置一个标志;

next_node = node->next;
node = (struct node*)((unsigned long)node | 0x1UL);

注意上面的标志不会影响真正的节点地址,只会影响保存的节点指针值。

一旦发现有人设置了标志位,那么第一个找到的节点应该是合并点。 完成后,您将通过清除已设置的标志位来恢复节点地址。但重要的是,在迭代(例如node=node->next)进行清理时应小心。记住你已经设置了标志位,所以这样做

real_node = (struct node*)((unsigned long)node) & ~0x1UL);
real_node = real_node->next;
node = real_node;

由于此方案将恢复修改后的节点地址,因此可以将其视为“无修改”。

此解决方案只迭代每个列表一次…不需要修改列表..尽管您可能会抱怨空间..
1)基本上,您在列表1中迭代,并将每个节点的地址存储在一个数组中(该数组存储无符号int值)。
2)然后迭代列表2,对于每个节点的地址--->搜索找到匹配项或不匹配项的数组…如果这样做,则这是合并节点。

//pseudocode
//for the first list
p1=list1;
unsigned int addr[];//to store addresses
i=0;
while(p1!=null){
  addr[i]=&p1;
  p1=p1->next;
}
int len=sizeof(addr)/sizeof(int);//calculates length of array addr
//for the second list
p2=list2;
while(p2!=null){
  if(search(addr[],len,&p2)==1)//match found
  {
    //this is the merging node
    return (p2);
  }
  p2=p2->next;
}

int search(addr,len,p2){
  i=0;  
  while(i<len){
    if(addr[i]==p2)
      return 1;
    i++;
  }
 return 0;
} 

希望这是一个有效的解决方案…

不需要修改任何列表。有一种解决方案,我们只需要遍历每个列表一次。

1. 创建两个堆栈,比如stck1和stck2。
2. 遍历第一个列表,并推送您在stck1中遍历的每个节点的副本。
3. 与第二步相同,但这次遍历第二个列表并推送stck2中的节点副本。
4. 现在,从两个堆栈中弹出并检查两个节点是否相等,如果相等,则保留对它们的引用。如果没有,那么之前相等的节点实际上就是我们要查找的合并点。

有一个简单的解决方案,但需要一个辅助空间。其思想是遍历一个列表并将每个地址存储在哈希图中,现在遍历另一个列表,如果地址是否位于哈希图中,则进行匹配。每个列表只遍历一次。没有对任何列表的修改。长度仍然未知。使用的辅助空间:o(n),其中“n”是遍历的第一个列表的长度。

这是一个幼稚的解决方案,不需要遍历整个列表。

如果结构化节点有三个字段,如

struct node {
    int data;   
    int flag;  //initially set the flag to zero  for all nodes
    struct node *next;
};

假设有两个标题(head1和head2)指向两个列表的标题。

以相同的速度遍历两个列表,并将该节点的标志设置为1(已访问标志)。

  if (node->next->field==1)//possibly longer list will have this opportunity
      //this will be your required node. 

这个怎么样?

1. 如果只允许遍历每个列表一次,则可以创建一个新节点,遍历第一个列表以使每个节点都指向此新节点,并遍历第二个列表以查看是否有任何节点指向新节点(即合并点)。如果第二次遍历没有引入新节点,那么原始列表没有合并点。

2. 如果允许您遍历列表多次,那么您可以遍历每个列表以查找它们的长度,如果它们不同,则省略较长列表开头的“额外”节点。然后一次只遍历两个列表中的一个步骤,并找到第一个合并节点。

Java中的步骤:

1. 创建一个地图。
2. 在列表的两个分支中开始遍历,并使用与节点相关的一些独特的东西(比如节点ID)作为键将列表的所有遍历节点放入映射中,并将值作为1放在起始位置。
3. 当第一个重复键出现时,递增该键的值(假设其值变为2,即>1)。
4. 获取值大于1的键,该键应该是两个列表正在合并的节点。

我们可以通过引入“isvisited”字段来有效地解决这个问题。遍历第一个列表,并将所有节点的“isvisived”值设置为“true”,直到结束。现在从第二个开始,找到第一个节点,其中标志是真的,然后是繁荣,它就是你的合并点。

步骤1:查找两个列表的长度 第二步:找到差异并移动最大的有差异的列表 第三步:现在两个列表将处于相似的位置。 步骤4:遍历列表以查找合并点

//Psuedocode
def findmergepoint(list1, list2):
lendiff = list1.length() > list2.length() : list1.length() - list2.length() ? list2.lenght()-list1.lenght()
biggerlist = list1.length() > list2.length() : list1 ? list2  # list with biggest length
smallerlist = list1.length() < list2.length() : list2 ? list1 # list with smallest length


# move the biggest length to the diff position to level both the list at the same position
for i in range(0,lendiff-1):
    biggerlist = biggerlist.next
#Looped only once.  
while ( biggerlist is not None and smallerlist is not None ):
    if biggerlist == smallerlist :
        return biggerlist #point of intersection


return None // No intersection found

int FindMergeNode(Node *headA, Node *headB)
{
    Node *tempB=new Node;
    tempB=headB;
   while(headA->next!=NULL)
       {
       while(tempB->next!=NULL)
           {
           if(tempB==headA)
               return tempB->data;
           tempB=tempB->next;
       }
       headA=headA->next;
       tempB=headB;
   }
    return headA->data;
}

使用map或dictionary存储节点的地址和值。如果地址已经存在于地图/字典中,则键的值就是答案。 我这样做了:

int FindMergeNode(Node headA, Node headB) {

Map<Object, Integer> map = new HashMap<Object, Integer>();

while(headA != null || headB != null)
{
    if(headA != null && map.containsKey(headA.next))
    {
        return map.get(headA.next);
    }

    if(headA != null && headA.next != null)
    {
         map.put(headA.next, headA.next.data);
         headA = headA.next;
    }

    if(headB != null && map.containsKey(headB.next))
    {
        return map.get(headB.next);
    }

    if(headB != null && headB.next != null)
    {
        map.put(headB.next, headB.next.data);
        headB = headB.next;
    }
}

return 0;
}

O(N)复杂性解决方案。但基于一个假设。

假设是:两个节点都只有正整数。

逻辑:使list1的所有整数都为负数。然后遍历列表2,直到得到一个负整数。找到后=>拿着它,将符号改回正数并返回。

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {

    SinglyLinkedListNode current = head1; //head1 is give to be not null.

    //mark all head1 nodes as negative
    while(true){
        current.data = -current.data;
        current = current.next;
        if(current==null) break;
    }

    current=head2; //given as not null
    while(true){
        if(current.data<0) return -current.data;
        current = current.next;
    }

}