LeetCode | 160. 相交链表
- 我们这里有两个问题，一是判断是否相交，二是找交点
思路一： 暴力求解
A链表所有节点依次取B链表找一遍（时间复杂度是O(N^2)）
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *headBbak = headB; while(headA != NULL) { while(headB != NULL) { if(headA == headB) return headA; headB = headB->next; } headA = headA->next; headB = headBbak; } return NULL; }
思路二： 优化->要求时间复杂度到O(N)
分别找到尾结点，尾节点地址相同就相交
分别找到尾结点，尾节点地址不相同就不相交
分别求出A和B的长度~~
长的先走差距步，再同时走，第一个相同的就是交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA, *curB = headB; //计算长度 int lenA = 1,lenB = 1; while(curA->next) { lenA++; curA = curA->next; } while(curB->next) { lenB++; curB = curB->next; } //判断相交 while(curA != curB) { return NULL; } int n = abs(lenA - lenB); //假设headA长，headB短 struct ListNode* longList = headA, *shortList = headB; if(lenA < lenB) { longList = headB; shortList = headA; } //让长链表先走n步 while(n--) { longList = longList->next; } //两个链表同时走，直到遇到相同的节点 while(longList != shortList) { longList = longList->next; shortList = shortList->next; } //相遇了，直接return return longList; }
