算法笔记-链表

发表于 | 分类于 ，

​ 链表和数组有点相似，但是它的元素之间是由一个指针相连接的，而且它要读取某一个元素的话也不能一下子就找到它，而是要遍历整个链表。由于链表的结构具有重复性、复杂性，所以很多链表的题目都用到了递归和分解步骤的方法。还有一点就是要善用指针，很多问题用指针就可以很巧妙地完成，当然这个指针的数量不一定唯一，例如在找环的时候，指针就有快慢指针。还有就是借用其他的数据结构，也就是用空间来换时间的方法。这几种方法都有一些地方需要注意，否则很容易就出错。

一.递归问题

来看几个递归题的例子。

  1. 输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

    这个要求的输出是一个链表，由于链表的结构具有重复性，所以可以用递归的方法来完成。递归的方法看起来逻辑也很清楚。

    1
    2
    3
    4
    5
    6
    # 返回从尾部到头部的列表值序列，例如[1,2,3] 
    def printListFromTailToHead(self, listNode): 
        # write code here 
        if listNode is None: 
            return [] 
        return self.printListFromTailToHead(listNode.next) + [listNode.val]

    这个方法只用了三行，递归方法的结构一般就是“递归出口+一般情况的处理+下一个递归入口“。写的时候就按这个结构去写，一般不会出错。这里下一个递归入口是包含在一般情况的处理当中的。然后递归的返回式一般是由函数组成的，函数即结果，我们这个时候就忽略函数里面的细节，把它当成是正确的返回结果就行了，这样理解起来，或者写起来就不会感觉很乱。
    这题的非递归解法就需要借用到其他的数据结构，栈。利用栈的FILO的性质来完成链表的倒置。

  2. 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

    这题是一个比较难的题目，因为它不仅仅考察了一个数据结构的性质，它考察了链表和二叉搜索树的性质，这题如果不知道二叉树的中序遍历的结果是一个升序结果的话，那就做不出来。递归的思想就是按递归的结构去思考问题。首先我们要清楚递归出口是什么，在这里就是如果两种情况：输入的节点不存在，则直接返回空。或者该节点不存在孩子，那么就直接返回该节点。接着思考一般情况下的处理，这个一般情况就是中序遍历：首先完成左边的子树遍历，然后再遍历根节点，接着最后完成右边的子树遍历。这个过程还要转换链表，所以首先我们左边的结果就是另一个递归的过程，在这个递归中，我们将它看成是已经完成的结果，也就是它返回的东西已经是一个双向链表了。这样就不用去纠结左子树到底是什么情况了。这个时候我们再把根节点接上去，当然这里要考虑左子树为空的情况。右边也是一样的操作。最后返回的值一定是一个双向链表。这里要注意。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        if pRootOfTree.left ==None and pRootOfTree.right == None:
            return pRootOfTree
        # 左子树生成双向链表
        left = self.Convert(pRootOfTree.left)
        # 找到左子树的最右边的节点
        p = left 
        while left and p.right:
            p = p.right
        # 将根节点加入到左子树的双向链表中
        if left :
            p.right = pRootOfTree
            pRootOfTree.left = p
        # 右子树生成双向链表
        right = self.Convert(pRootOfTree.right)
        # 将右子树的双向链表加入前面的链表中。
        if right :
            right.left = pRootOfTree
            pRootOfTree.right = right
        return left if left else pRootOfTree

二.复杂问题分解成n个步骤

将复杂问题分解成小问题，然后再依次去解决这些小问题。这个方法用在哪里都不会有错，首先将问题模块化分解，就比较容易找出我们在哪一步出错，其次，这也容易让我们缕清解题的思路，逻辑上不容易混。这里要注意全局变量和局部变量的区别。我们使用小问题解决问题，也可以解决指针变量变化的问题。这个复杂问题分解要不要写成许多函数的形式也要具体看问题分析。

1.输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。

看上图的分析应该就知道问题要怎么分解了，然后实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 返回 RandomListNode
def Clone(self, pHead):
    # write code here
    #分成三步，复制，生成链接，分离
    if not pHead:
        return None
    dummy = pHead
    
    while dummy:
        dummyNext = dummy.next
        copyNode = RandomListNode(dummy.label)
        dummy.next = copyNode
        copyNode.next = dummyNext
        dummy = dummyNext
    
    dummy = pHead
    while dummy:
        copyNode = dummy.next
        dummyRandom = dummy.random
        if dummyRandom:
            copyNode.random = dummyRandom.next
        dummy = copyNode.next
        
    dummy = pHead
    copyHead = dummy.next
    while dummy:
        copyNode = dummy.next
        dummyNext = copyNode.next
        dummy.next = dummyNext
        if dummyNext:
            copyNode.next = dummyNext.next
        else:
            copyNode.next = None
        dummy = dummyNext
    return copyHead

2.输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

在这一题中，我们需要两个链表的长度，读取链表长度的方法就是去遍历这个链表，然后累加节点的数量。

1
2
3
4
5
res = 0
while Head:
    Head = Head.next
    res += 1
return res

像这么写的话就要小心了，因为在这里我们是直接拿Head去遍历的，这样一来的话Head就会移动到链表的尾部，也就是None，之后就找不到表头了，所以这一段最好写成函数的形式，或者是另设一个变量去遍历。完整的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def FindFirstCommonNode(self, pHead1, pHead2):
    # write code here
    if not pHead1 or not pHead2:
        return None
    def count_num(Head):
        res = 0
        while Head:
            Head = Head.next
            res += 1
        return res
    num_pHead1 = count_num(pHead1)
    num_pHead2 = count_num(pHead2)
    if num_pHead1 > num_pHead2:
        for i in range(num_pHead1-num_pHead2):
            pHead1 = pHead1.next
    if num_pHead2 > num_pHead1:
        for i in range(num_pHead2-num_pHead1):
            pHead2 = pHead2.next
    while pHead1 != None and pHead2 != None and pHead1 != pHead2:
        pHead1 = pHead1.next
        pHead2 = pHead2.next
    return pHead1

三.指针的作用

指针用得好，链表没烦恼。很多问题需要借用指针来完成，简单的，遍历、获取链表的长度等。解题过程就像是缝衣服，指针就像是针线一样，起到了关键的作用，用得巧的话，很多题目可以在很低的复杂度下完成，当然，这种解法相对来说也比较复杂。

1.输入一个链表，反转链表后，输出新链表的表头。

这里是借助了两个指针和一个临时的指针完成的，真的就像是缝衣服一样。一般这类题目都需要两个指针以上，一个指针指向当前的指针，也就是遍历的位置，然后一个指针指向后一个节点的位置，避免找不到链表，然后一些其他的辅助指针。像这题就是需要一个指向当前指针的前面一个指针，完成链表的反转。

1
2
3
4
5
6
7
8
9
10
11
12
def ReverseList(self, pHead):
    # write code here
    if not pHead or pHead.next == None :
        return pHead
    pPre = None
    pThis = pHead
    while pThis != None:
        tmp = pThis.next
        pThis.next = pPre
        pPre = pThis
        pThis = tmp
    return pPre
请作者喝杯咖啡吧！