單鏈表求交點，問題如下：

使用o(1)的空間復雜度，求兩個鏈表相交的時候的交點，這個思想就類似于使用o(1)的空間復雜度和o(n)的時間復雜度來求鏈表的第k個節(jié)點。

過程如下：

1. 獲取兩個鏈表的長度
2. 將較長的鏈表移動和短鏈表長度差值的位置
3. 移動后兩個鏈表長度一樣，然后一起移動，這樣就知道節(jié)點相等的時候鏈表相交
   

算法實現(xiàn)如下:get_intersection_node函數(shù)

/*獲取交叉鏈表的節(jié)點*/
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) {/*本代碼用于測試，根據(jù)鏈表的data域進行判斷，正規(guī)是判斷兩鏈表指針域是否相等*/if(headA->data == headB->data) {return headA;}headA = headA -> next;headB = headB -> next;}return NULL;
}

源碼實現(xiàn)如下：

#include <stdio.h>
#include <stdlib.h>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("\n");
}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;
}/*獲取交叉鏈表的節(jié)點*/
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) {/*本代碼用于測試，根據(jù)鏈表的data域進行判斷，正規(guī)是判斷兩鏈表指針域是否相等*/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 :\n");headA = insert_tail(headA,5);printf("construct second link list :\n");headB = insert_tail(headB, 3);result = get_intersection_node(headA,headB);if (result){printf("intersection node is %d\n",result -> data);}else {printf("there is no intersection node\n");}return 0;
}

輸出如下:

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

總結(jié)

以上是生活随笔為你收集整理的C语言的单链表求交点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。