leetcode Intersection of Two Linked Lists

发表于   |   分类于   |  

题目链接：Intersection of Two Linked Lists

题目描述(Description)

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:

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.

找到两个链表的交点

写一个程序找到两个链表的相交结点。

例如，如下有两个链表A,B：

A,B开始交汇于结点c1。

注意：

  • 如果两个链表没有交点，返回null

  • 在函数返回后，链表必须保持原来的结构不变

  • 你可以假设在整个的链表结构里没有环

  • 你的代码时间复杂度为O(n)，空间复杂度O(1)。

分析(Analysis)

  1. 对于两个链表A,B，如果有交点，那么它们的尾指针必定重合，以此判断两链表是否相交。

  2. 如果A,B相交，把相交前的部分和相交后的部分分开来看，相交后的部分链表长度是一样的，那么如果两链表不一样长，则只可能是相交前部分不一样长。分别统计出两链表的长度lenA和lenB，然后做差值d，把较长的链表头指针向移动d个结点，然后再同时移动两个链表的头指针，如果头指针相同，就是我们要找的相交结点。

代码(Code)

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