前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Q160 Intersection of Two Linked Lists

Q160 Intersection of Two Linked Lists

作者头像
echobingo
发布2018-04-25 16:53:02
5020
发布2018-04-25 16:53:02
举报
文章被收录于专栏:Bingo的深度学习杂货店

Write a program to find the node at which the intersection of two singly linked lists begins.

代码语言:javascript
复制
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.
解题思路:

此题需要注意的两点是返回后,需要保持原来的链表结构,同时对时间复杂度的要求为 O(n),空间负责度的要求为 O(1)。

由于空间复杂度的限制,故排除用Map保存一个链表结点,然后与另一个链表比对的方法。

观察到如果两个链表有相同的交集,那么它们从相同的结点开始,后面长度都是相同的。因此,可以先计算两个链表的长度,然后比较长度的差值 diff,较长的那个先走 diff 步,然后和较短的那个同时遍历。如果指针指向同一元素,则为交点,否则 A 和 B 没有交点。

Python实现:
代码语言:javascript
复制
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        A = A1 = headA; B = B1 = headB
        lenA = lenB = 0
        # 计算链表 A,B 的长度
        while A != None:
            lenA += 1
            A = A.next
        while B != None:
            lenB += 1
            B = B.next
        # 尾对齐链表
        if lenA > lenB:
            diff = lenA - lenB
            while diff > 0:
                A1 = A1.next
                diff -= 1
        else:
            diff = lenB - lenA
            while diff > 0:
                B1 = B1.next
                diff -= 1
        # 从对应的位置开始比较
        while A1 != None and B1 != None and A1.val != B1.val:
            A1 = A1.next
            B1 = B1.next
        return A1  # 或者返回B1
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.02.28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 解题思路:
  • Python实现:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档