【原创】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 - ) / ;
} ListNode *findNthNode(ListNode *head,int toN)
{
int count = ;
while (toN != count)
{
head = head->next;
count ++;
}
return head;
} int countLength(ListNode *head,int *fin)
{
int count = ;
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 ()
{
now->next = pre;
pre = now;
now = nxt;
if (nxt)
nxt = nxt->next;
else
break;
}
}
};
上一篇:cocos2d-x3.2中怎样优化Cocos2d-X游戏的内存


下一篇:iOS 组件化路由框架 WisdomRouterKit 的应用