链表

Posted on Edited on In ,

算法通关村第一关————链表经典问题

1、五种办法解决两个链表的第一个公共子节点问题

问题描述：输入两个链表，找出它们的第一个公共结点。

我的思路：（之前没练过算法，所以会有些笨，也叫暴力解法？），先检测链表是否符合链表要求，然后进行遍历对比，找到一个相同节点（值和存储的next都相同），返回该节点。这里应该用两个for循环，一个遍历链表1，另嵌套进去遍历链表2，然后逐个进行对比，找到相同的节点，返回该节点。

1.1、暴力解法

这个就是我想出来的办法了

像冒泡排序一样，两个for循环，一个遍历链表1，另嵌套进去遍历链表2，然后逐个进行对比，找到相同的节点，返回该节点。但时间复杂度太高，不建议使用。

1.2、hash表法

这里得对hash进行初步的理解，我们可以这样想，hash可以认为是一个用于查找的参考书，我们把一个链表加入参考书后，只需循环另一个链表，查看参考书是否有该节点，如果有，那就找到了该节点。
这里用了pythons的set集合，set集合是哈希表的实现，所以查找速度非常快。

1
2
3
4
5
6
7
8
9
10
11
12
13
# hash集合版
def getIntersectionNodebyHash( self, pHead1, pHead2):
    s = set()#创建一个集合
    p,q = pHead1,pHead2
    while p:#遍历p
        s.add(p)#把p全部都加入集合中
        p = p.next
    while q:#遍历q
        if q in s:#把q中的内容对s一一比对，看是否有相同节点
            return q
        q = q.next
    return None

1.3、栈法

这里我们得先理解栈的概念，这里的栈，可以理解为一个存储数据的容器，先进后出，后进先出。

可以知道的是，无论两个链表前面有多不同，它们最后都会到达一个相同的节点，所以我们可以把两个链表的节点都存入栈中，然后一一比对，找到相同的节点，返回该节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 栈版
def getIntersectionNode( self, pHead1, pHead2):
    s1,s2 = [],[]#创建两个数组
    p,q = pHead1,pHead2
    while p:
        s1.append(p)#把p全部压入s1中
        p = p.next#更新“指针”
    while q:
        s2.append(q)
        q = q.next
    p,q = s1.pop(),s2.pop()#把p和q用s1代替
    while p and q:#从栈顶取数
        if p == q:
            return p
        p,q = s1.pop(),s2.pop()
    return None

1.4、双指针

2、判断链表是否为回文序列

问题描述

3. 合并有序链表

问题描述