首页 > 代码库 > 剑指offer (37) 两个链表的第一个公共结点

剑指offer (37) 两个链表的第一个公共结点

2024-07-09 16:51:32   215人阅读

题目：输入两个链表，找出它们的第一个公共结点

如果两个链表有公共结点，那么公共结点一定出现在两个链表的尾部

如果两链表长度不相等，那么达到公共结点的步数就不一致，如何确保 两个链表从头开始遍历，同步达到公共结点？ 这是关键所在

如果两链表长度相同，那么就可以同步达到了？ 由此，我们就需要 让两个链表长度"相等"

我们假设 两链表长度分别为m和n，且m > n， 那么我们可以在较长链表中 先走 m - n 步，然后 两个链表游标同步走，如果有公共结点，那么就一定同时达到

ListNode* FirstCommonNode(ListNode* list1, ListNode* list2){    if (list1 == NULL || list2 == NULL)  return NULL;    ListNode* cur1 = list1;    ListNode* cur2 = list2;    int list1Len = 0;    int list2Len = 0;    while (cur1++ != NULL) { ++list1Len; }    while (cur2++ != NULL) { ++list2Len; }    int maxLen = std::max(list1Len, list2Len);    ListNode* longerList = NULL;    ListNode* shorterList = NULL;    int gap = 0;    if (maxLen == list1Len) {        longerList  = list1;        shorterList = list2;        gap = maxLen - list2Len;    } else {        longerList  = list2;        shorterList = list1;        gap = maxLen - list1Len;    }    int firstStep = 0;    while (firstStep != gap) {        longerList = longerList->next;        ++firstStep;    }    while (longerList != NULL && shorterList != NULL) {        if (longerList == shorterList) {            return longerList;        } else {            longerList  = longerList->next;            shorterList = shorterList->next;        }    }    return NULL;}

 


联系
我们