[leetcode]Intersection of Two Linked Lists　——　相熟python

[leetcode]Intersection of Two Linked Lists　——　熟悉python

好久没有耍代码了，手有点生，还有点痒，and 脑子有点锈。话说这个简单的东西，耍了我一个小时。

主要是最近很少碰代码。二是对python不熟悉，刚刚接触，但是顿时很热爱这个小蟒蛇。于是打算好好蹂躏它。

题目链接：https://oj.leetcode.com/problems/intersection-of-two-linked-lists/

我的思路是这样的。

首先没有循环，所以不用判断是否绕一圈回来了。其次，看题意不会有多次分支，即分支只有一个，且一直相同到尾部。那么好办了。

我只需要逆向判断字符串是否相等就好了。

最后一个字符不相等。直接pass；反之，一直比较到看到不同的字符为止，输出就好了。

以上是我在实现之前的简单想法，貌似可行。但是实际实现的时候，发现很多细节问题遗漏了。这也是我很久没有摸代码的一个后果。

比如，碰到输入链表是空的，要处理；碰到一个字符串是另一个的子集，即在完成比较之前，就退出循环了，要处理；还有几个循环边界的问题。

所以说，感觉还是多码豆豆有好处。码豆豆给了我深度思考的习惯。

ok，上代码：

Runtime: 1576 ms 42 / 42 test cases passed.

# 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):
        listA = []
        listB = []
        if headA == None or headB == None:# 判断输入表是否为空
            return None
            
        while 1:#链表赋值到list中，方便从后面比较
            if headA == None:
                break;
            listA.append(headA.val)
            headA = headA.next
        while 1:
            if headB == None:
                break;
            listB.append(headB.val)
            headB = headB.next
            
        if listA[-1] != listB[-1]:# list最后一个元素不等
            return None;
        if len(listA)<len(listB):# 以最短链表长度为准比较
            minLen = len(listA)
        else:
            minLen = len(listB)
            
        inster = []
        for i in range(1,minLen+1) # 边界问题，因为是逆向获取数据，因此，比较到第一个元素的时候。 listA[0] = listA[-len]
            if listA[-i] != listB[-i]:
                return ListNode(listA[-i+1])
            if i== maxLen:    #处理两个表存在子集的情况
                return ListNode(listA[-i])

【总结一下】python中，list元素会出现index out of length的情况。python的基础不熟悉，产生了低级错误，应当多注意对list内容的审核，过滤。另，写的python程序总是不简洁。始终有c的影子在里面。得多写写。

另外，作者的solution是这样的，提供了三个方法：

1、暴力搜索：对headA中每个元素，分别比较headB中每个元素。 0(mn)

2、hash表方法：对每个元素的address和值建立hash，第一个相等的，获取address。 python里面，可以用字典了。

3、两个指针的方法：这个方法有人实现了。因为这个题目的特殊性，通过让较长的链表多走比较短链表长的步数，再同时移动两个链表的指针进行比较搜索的方法。实现的算法。总之都是简答题，权当熟悉语法。

keep on coding！

[leetcode]Intersection of Two Linked Lists —— 相熟python

相关推荐

[leetcode]Intersection of Two Linked Lists　——　相熟python