【leetcode】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.

解题思路:

首先这道题目有他的特殊性,这个特殊性就在这里的两个链表如果有交集的话,那么他们在最后面的一定都是相同的。

所以这里催生了两种想法:

  1. 从后往前比较,找到最后形同的那个

  2. 从前往后比较,但是这里要用到一个技巧。我们首先要去获取到这两个链表的长度,然后让长度长的那个先多走长度差的距离,最后再开始比较,第一个相同的即是。

    这里使用了第二种思路:

    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):

    ta = ListNode(0)

    tb = ListNode(0)

    ta = headA

    tb = headB

    la = 0

    lb = 0

    while ta != None:

    la += 1

    ta = ta.next

    while tb != None:

    lb += 1

    tb = tb.next

    if la > lb :

    ta = headA

    tb = headB

    tt = la - lb

    while tt > 0:

    ta = ta.next

    tt -= 1

    while ta != None and tb != None:

    if ta == tb:

    return ta

    ta = ta.next

    tb = tb.next

    return None

         else:
    ta = headA
    tb = headB
    tt = lb -la
    while tt > 0:
    tb = tb.next
    tt -= 1
    while ta != None and tb != None:
    if ta.val == tb.val:
    return ta
    ta = ta.next
    tb = tb.next
    return None
上一篇:Linux命令行下载文件百度云盘


下一篇:IOS获取摄像和本地中的资源