首页 > 代码库 > 【原创】leetCodeOj --- Intersection of Two Linked Lists 解题报告(经典的相交链表找交点)
【原创】leetCodeOj --- Intersection of Two Linked Lists 解题报告(经典的相交链表找交点)
题目地址：
https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
题目内容：
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3
begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return
null. - The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
方法：
首先，既然是时间复杂度O(n)，那么就不能一个一个点那样试；
其次，既然空间复杂度要求O(1)，既然就不能用stack或者unordered_map之类的数据结构来找链表交点。
那么，我们需要一个比较酷炫的trick来找交点。
先转化问题：
假设有A、B两条链表相交，请求出交点到A链表头结点的距离。（所谓距离，就是头结点走几次能到）
先看具体求法：
0、计算A链表的长度lenA
1、计算B链表的长度lenB
2、逆转A链表（关键）
3、重新计算B链表的长度newLenB
4、返回result = (newLenB - lenB + lenA - 1) / 2
具体到这道题，还需要把A链表又逆转回来，因为你不能更改链表原来的结构。然后重新读取链表，返回第result个结点就OK了。
那么这具体求法究竟是怎么来的？
自己动手试试就明白了。其实就是算出A链表结点在交点旁边的分布数，画图太麻烦了，如果有时间再补一个，或者谁不理解回复一下我就补
全部代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { if (headA == NULL || headB == NULL) return NULL; int addressA; // fin of A. int addressB; // fin of B. int lenA = countLength(headA,&addressA); int lenB = countLength(headB,&addressB); if (addressA != addressB) // if has a intersect return NULL; ListNode *tmpHeadA = (ListNode *)addressA; // to store headA‘s tail for reverse. reverseLink(headA); int newLenB = countLength(headB,&addressB); int toNew = findCount(lenA,lenB,newLenB); reverseLink(tmpHeadA); return findNthNode(headA,toNew); } int findCount(int lenA,int lenB,int newLenB) { int gap = newLenB - lenB; return (gap + lenA - 1) / 2; } ListNode *findNthNode(ListNode *head,int toN) { int count = 0; while (toN != count) { head = head->next; count ++; } return head; } int countLength(ListNode *head,int *fin) { int count = 0; while (head) { *fin = (int)head; head = head->next; count ++; } return count; } void reverseLink(ListNode *head) { ListNode *pre = NULL; ListNode *now = head; ListNode *nxt = head->next; while (1) { now->next = pre; pre = now; now = nxt; if (nxt) nxt = nxt->next; else break; } }};
【原创】leetCodeOj --- Intersection of Two Linked Lists 解题报告(经典的相交链表找交点)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。