【一天一道LeetCode】#160. Intersection of Two Linked Lists

一天一道LeetCode

（一）题目

（二）解题

题目大意：两个单向链表，有一段重复区域，找出其中的第一个交叉节点。

解题思路：题目要求时间复杂度O(n)和空间复杂度O(1)，所以利用辅助空间的方法都不行。

如果两个链表会交叉，那么他们的最后一个节点肯定相同，如果是双向链表，可以从尾节点开始，找到第一个出现分离的节点即可。可是，题目要求不能破坏初始链表。这种方法也行不通。

如果两个链表的长度一样的话，从头开始往后，可以找到第一个交叉点。

记链表的长度为len1和len2，可以让长链表先走abs(len1-len2)步，再两个一起往后找。即可找到第一个交叉点。

具体解释见代码：

/**
 * 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) {
        int lenA = getlength(headA);//统计链表A的长度
        int lenB = getlength(headB);//统计链表B的长度
        int diflen = lenA-lenB;//计算差值
        //lenA<lenB的情况
        ListNode *longList = headA;//lenA<lenB的情况
        ListNode *shortList = headB;
        //lenA>lenB的情况
        if(diflen<0)
        {
            longList = headB;
            shortList = headA;
            diflen = -diflen;
        }
        while(diflen>0&&longList!=NULL)//让长链表先走diflen步
        {
            longList = longList->next;
            diflen--;
        }
        while(longList!=NULL&&shortList!=NULL)//两个链表一起往后走
        {
            if(longList->val == shortList->val) return longList;//找到交叉节点
            else{
                longList = longList->next;
                shortList = shortList->next;
            }
        }
        return NULL;
    }
    int getlength(ListNode *head)
    {
        int n = 0;
        ListNode *phead = head;
        while(phead!=NULL)
        {
            phead = phead->next;
            n++;
        }
        return n;
    }
};