［LeetCode］Intersection of Two Linked Lists-白红宇

［LeetCode］Intersection of Two Linked Lists

阅读量：2235 次

发布时间：2019-05-09

本文共 1539 字，大约阅读时间需要 5 分钟。

思路：

条件比较严：

1，不破坏数据结构；

2，时间复杂度O(n)，空间复杂度O(1)

3，假设没有环路；

4，没有交点，返回null

反过来想，从链表的结尾开始，向链表header开始数，对同一个index对应的node，链表A和B的address在intersection之前都是相等的，在intersection之后开始不同。

但题目所述链表非双向list，我们必须list的header开始，向后找intersection。所以，我们必须找到一个node，在这个node之后，链表A和B是等长的

1，先决条件：计算链表A和B的长度，初始化链表A和B的游标CurA 和CurB，较长的链表的游标Cursor移动 | A.length - B.length|个单位

2，不变式：比较CurA 和CurB的address

3，结束条件：address相同，或者同时为null

4，临界条件：链表A和B不为null

//编译错误

1，调用结构体指针的value，要用 “ -> “

// Runtime Error;

1，没有初始化 CurA 和CurB

/** * 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 lenA = 0;        int lenB = 0;        ListNode *p = headA;        while (p != NULL){            lenA ++;            p = p->next;        }        p = headB;        while (p != NULL){            lenB ++;            p = p->next;        }        ListNode *curA = headA;        ListNode *curB = headB;        if (lenA > lenB){            int i = 0;            while (i < lenA - lenB){                curA = curA->next;                i ++;            }        }else if (lenB > lenA){            int i = 0;            while (i < lenB - lenA){                curB = curB->next;                i ++;            }        }        while (curA != curB){            curA = curA->next;            curB = curB->next;        }        return curA;    }};

转载地址：http://lcpbb.baihongyu.com/

你可能感兴趣的文章