一起刷leetcode(160) : 寻找两个链表的交点


编程:寻找两个链表的交点。
leetcode.PNG

/**
* 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) {


}
};

注意:
如果两个链表没有交点,则返回null
程序比能改变链表的原有结构
相交的两个链表之间不会构成环
要求:O(n)时间复杂度, O(1)空间复杂度

欢迎把刷leetcode题的代码发上来,一起刷leetcode!
已邀请:

sumnous - 数据挖掘女博士

赞同来自: HeroJack sjf0115 lvraikkonen drenched_bj prosoul


思路:双指针解法 ,时间复杂度O(n+m),空间复杂度O(1):

维护两个指针pA和pB,初始分别指向A和B。然后让它们分别遍历整个链表,每步一个节点。

当pA到达链表末尾时,让它指向B的头节点;类似的当pB到达链表末尾时,重新指向A的头节点。

如果pA在某一点与pB相遇,则pA或pB就是交点。

所以最多遍历 链表A的长度+链表B的长度 即可判断出是否有相交的节点。

Python代码(已AC):
    # Definition for singly-linked list.
    #class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        pA = headA
        pB = headB
        if headA == None or headB == None:
            return
        while pA and pB:
            if pA.val != pB.val:
                if pA.next and pB.next:
                    pA = pA.next
                    pB = pB.next
                elif pA.next == None and pB.next != None:
                    pA = headB
                    pB = pB.next
                elif pB.next == None and pA.next != None:
                    pA = pA.next
                    pB = headA
                else:
                    return
            else:
                return pA #之前返回pA.val,在这里卡好一会儿,注意返回ListNode实例,而不是节点值!!


坚持不懈刷Leetcode!

要回复问题请先登录注册