首页 > 代码库 > [C++]LeetCode: 60 Intersection of Two Linked Lists

[C++]LeetCode: 60 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.

Answer 1: 双指针法

思路:由于本题题意指合并,即如果两个链表有共同节点,尾部节点一定是同一个节点,即Y型。

设定两个指针,若从两个链表的表头同时遍历,很明显不能找到交点。但如果先将较长的链表截取长出去的一部分,然后两个链表同时遍历,则第一次两个指针相等的节点明显是所求节点。但若走到链表尾,仍然未相交,则两个链表未相交。

Attention:

1. 如何计算两个链表长度。

分别遍历链表,记录其长度。

 while(pa) {pa=pa->next;lengthA++;}  
 while(pb) {pb=pb->next;lengthB++;}  
2. 需要保存链表头结点,以备后面恢复链表指针需要。
 ListNode *pa=headA,*pb=headB; 
复杂度:O(lengthA + lengthB) .空间复杂度O(1)

AC 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) {
        ListNode* pa = headA;
        ListNode* pb = headB;
        
        //记录ListA和ListB的长度
        int lengthA = 0;
        int lengthB = 0;
        while(pa)
        {
            pa = pa->next;
            lengthA++;
        }
        while(pb)
        {
            pb = pb->next;
            lengthB++;
        }
        
        //由于本题题意指合并,即如果两个链表有共同节点,尾部节点一定是同一个节点,即Y型,先将两个链表移动到节点个数一致的地方
        if(lengthA >= lengthB)
        {
            int n = lengthA - lengthB;
            pa = headA;
            pb = headB;
            while(n)
            {
                pa = pa->next;
                n--;
            }
        }
        else
        {
            int n = lengthB - lengthA;
            pa = headA;
            pb = headB;
            while(n)
            {
                pb = pb->next;
                n--;
            }
        }
        
        while(pa != pb)
        {
            pa = pa->next;
            pb = pb->next;
        }  
        return pa;
    }
};

Answer 2: 追逐法(更加简练)

思路:根据追逐步长相同的方法,判断出如果两个链表存在交叉点,下次相遇一定在交叉点,否则在尾部节点。

算法:保存两个链表头结点,同步遍历,如果某指针达到末尾,则将其指向另外一个链表头结点。直到有相同节点或者都为NULL.

复杂度:O(lengthA + lengthB)

看下面的示意图就可以清晰明白。

技术分享

AC 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) {
        ListNode* pa = headA;
        ListNode* pb = headB;
        
        if(pa == NULL || pb == NULL) return NULL;
        
        while(pa != NULL && pb != NULL && pa != pb)
        {
            pa = pa->next;
            pb = pb->next;
            
            if(pa == pb) return pa;
            
            //追逐,下次相遇一定是在交叉点,如果没有交叉点,即终点。
            if(pa == NULL) pa = headB;
            if(pb == NULL) pb = headA;
        }
        
        return pa;
    }
};



[C++]LeetCode: 60 Intersection of Two Linked Lists