检查两个链表是否相交，如果相交，找出交点的位置。

这里有一个简单的解决方案，但需要使用辅助空间。思路是遍历一个列表并将每个地址存储在哈希映射中，现在遍历另一个列表并匹配地址是否存在于哈希映射中。每个列表只被遍历一次，不对任何列表进行修改，长度仍未知。所需辅助空间：O（n），其中'n'是遍历第一个列表的长度。

//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. 现在，从两个堆栈中弹出并检查两个节点是否相等，如果是，则保留对它们的引用。如果不是，则先前相等的节点实际上是我们正在寻找的合并点。

int FindMergeNode(Node headA, Node headB) {
  Node currentA = headA;
  Node currentB = headB;

  // Do till the two nodes are the same
  while (currentA != currentB) {
    // If you reached the end of one list start at the beginning of the other
    // one currentA
    if (currentA.next == null) {
      currentA = headA;
    } else {
      currentA = currentA.next;
    }
    // currentB
    if (currentB.next == null) {
      currentB = headB;
    } else {
      currentB = currentB.next;
    }
  }
  return currentB.data;
}

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode* start1=head1;
    SinglyLinkedListNode* start2=head2;
    while (start1!=start2){
        start1=start1->next;
        start2=start2->next;
        if (!start1)
        start1=head2;
        if (!start2)
        start2=head1;
    }
    return start1->data;
}

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;
    }

}

使用Map或Dictionary来存储节点的地址和值。如果地址已经存在于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;
}

这里是一个天真的解决方案，不需要遍历整个列表。

如果你的结构化节点有三个字段，比如

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. 如果允许多次遍历列表，则可以遍历每个列表以找到它们的长度，如果它们不同，则省略较长列表开头的“额外”节点。然后只需一次一步地遍历两个列表，并找到第一个合并节点。