单链表求交点，问题如下：



使用o(1)的空间复杂度，求两个链表相交的时候的交点，这个思想就类似于使用o(1)的空间复杂度和o(n)的时间复杂度来求链表的第k个节点。

过程如下：

1. 获取两个链表的长度
2. 将较长的链表移动和短链表长度差值的位置
3. 移动后两个链表长度一样，然后一起移动，这样就知道节点相等的时候链表相交
   
   

算法实现如下:get_intersection_node函数

/*获取交叉链表的节点*/
Data *get_intersection_node(Data *headA, Data *headB) { int lenA;int lenB;lenA = get_len(headA);lenB = get_len(headB);/*平衡较长的链表，缩减长度*/if (lenA > lenB) { headA = equal_link(lenA,lenB,headA);} else { headB = equal_link(lenB,lenA,headB);}while(headA && headB) { /*本代码用于测试，根据链表的data域进行判断，正规是判断两链表指针域是否相等*/if(headA->data == headB->data) { return headA;}headA = headA -> next;headB = headB -> next;}return NULL;
}

源码实现如下：

#include 
#include typedef struct link_list { int data;struct link_list *next;
}Data;void print_list(Data *head) { while (head) { printf("%d ",head->data);head = head -> next;}printf("
");
}Data *insert_tail(Data *head, int n) { head = (Data *)malloc(sizeof(Data));head -> next = NULL;Data *r = head;int data;while(n--) { Data *p = (Data *)malloc(sizeof(Data));scanf("%d", &data);p -> data = data;r -> next = p;r = p;p -> next = NULL;}return head;
}/*获取链表的长度*/
int get_len(Data *head) { int len = 0;while (head -> next) { len ++;head = head -> next;}return len;
}/*将较长的链表长度缩减指定的差值*/
Data *equal_link(int longLen, int shortLen, Data *head) { int delta = longLen - shortLen;while (head && delta) { head = head -> next;delta --;}return head;
}/*获取交叉链表的节点*/
Data *get_intersection_node(Data *headA, Data *headB) { int lenA;int lenB;lenA = get_len(headA);lenB = get_len(headB);if (lenA > lenB) { headA = equal_link(lenA,lenB,headA);} else { headB = equal_link(lenB,lenA,headB);}while(headA && headB) { /*本代码用于测试，根据链表的data域进行判断，正规是判断两链表指针域是否相等*/if(headA->data == headB->data) { return headA;}headA = headA -> next;headB = headB -> next;}return NULL;
}
int main() { Data *headA;Data *headB;Data *result;printf("construct first link list :
");headA = insert_tail(headA,5);printf("construct second link list :
");headB = insert_tail(headB, 3);result = get_intersection_node(headA,headB);if (result){ printf("intersection node is %d
",result -> data);}else { printf("there is no intersection node
");}return 0;
}

输出如下:

construct first link list :
1 2 3 4 5
construct second link list :
3 4 5
intersection node is 3