[leetcode题解]160.Intersection of Two Linked Lists

leetcode第160题,给定两个链表的头节点,求两个链表是否相交,如果相交则返回相交的首节点,否则返回NULL。

思路是两个指针分别从头开始走,直到一个指针为NULL,这说明另一个链表比较长,而且长的这个链表剩下的节点个数正好是长度超出的节点数。这个时候把长的从头开始走,走的步数为整下的节点个数,这样短的节点从头开始,就能保证两者要走的节点数相同,也就是如果相交,那么两者分别走下去一定会在交点处碰头,否则,无交点。

python实现的时候一直memory limit exceed,而且不知道是什么原因,后来看discuss才看到,需要交gc.collect()。加了这句代码,就AC了。

c++代码:

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) 
    {
        ListNode *p = headA;
        ListNode *q = headB;
        
        while (p != NULL && q != NULL)
        {
            p = p->next;
            q = q->next;
        }
        
        if (p == NULL)
        {
            headB = move(q, headB);
        }
        else
        {
            headA = move(p, headA);
        }
        
        bool mark = false;
        while(headA != NULL && headB != NULL)
        {
            if (headA->val == headB->val)
            {
                mark = true;
                break;
            }
            headA = headA->next;
            headB = headB->next;
        }
        
        if (mark)return headA;
        return NULL;
    }
    
    ListNode *move(ListNode *p, ListNode *q)
    {
        while(p != NULL)
        {
            p = p->next;
            q = q->next;
        }
        return q;
    }
};

python代码:

import gc
class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA == None or headB == None:
            return None
        p = headA
        q = headB
        
        gc.collect()
        while p != None and q != None:
            p = p.next
            q = q.next
        
        print(headA.val)    
        print(headB.val)
        
        if p == None:
            headB = self.move(q, headB)
        else:
            headA = self.move(p, headA)
            
        print(headA.val)    
        print(headB.val)
        
        mark = False
        while headA != None and headB != None:
            if headA == headB:
                mark = True
                break
            headA = headA.next
            headB = headB.next
            
        if mark:
            return headA
        return None
        
    def move(self, p, q):
        while p != None:
            p = p.next
            q = q.next
        return q

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解]160.Intersection of Two Linked Lists

本文链接地址:http://www.iaccepted.net/algorithm/leetcode/58.html

相关文章



发表评论

电子邮件地址不会被公开。 必填项已用*标注