如何判断两个单链表是否相交

比较好的方法有两个：

一、将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。

二、如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

引申问题：如何判断一个链表是环形链表？

设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。直到p2碰到NULL指针或者两个指针相等结束循环。如果两个指针相等则说明存在环。时间复杂度为O（n）。

#include "stdafx.h"
typedef char eleType;                // 定义链表中的数据类型
typedef struct listnode {            // 定义单链表结构
     eleType data;
     struct listnode *next;
}node;

node *create(int n) {                 // 创建单链表，n为节点个数
     node *p = (node *)malloc(sizeof(node));  
     node *head = p;    head->data = 'A';
     for(int i='B'; i<'A'+n; i++) {
         p = (p->next = (node *)malloc(sizeof(node)));
         p->data = i;
         p->next = NULL;
     }
     return head;
}

void addCircle(node *head, int n) {  // 增加环，将链尾指向链中第n个节点
     node *q, *p = head;
     for(int i=1; p->next; i++) {
         if(i==n) q = p;
          p = p->next;
     }
     p->next = q;
}

int isCircle(node *head) {           // 这是笔试时需要写的最主要函数，其他函数可以不写
     node *p=head,*q=head;
     while( p->next && q->next) {
         p = p->next;
         if (NULL == (q=q->next->next))   return 0;
         if (p == q)   return 1;
     }
     return 0;
}

int main(int argc, char* argv[]) {
     node *head = create(12);
     addCircle(head, 8);              // 注释掉此行，连表就没有环了
     printf("%d\n", isCircle(head));
}