链表问题

发表于 | 分类于 ，

冲冲冲。

链表问题

链表和队列的区别在于指针，而指针问题又会涉及到遍历，多指针等特别的解法，同时也可以结合其他的数据结构来解链表问题，例如回文链表等。

1.约瑟夫环问题

题目：这道题目的变体很多，但是剥去词藻，其本质就是约瑟夫环问题。有m个人,围成一个环，编号为 0、1、2、3、、、m-1，从第一个人开始循环报数，假设数到n的那个人出列，然后从下一个人继续数数，数到n出列，以此循环，最后那个人为胜利者，求胜利者的编号。

分析：这道题目可以暴力求解，就是构造一个带环的链表，然后模拟整个过程，最后剩下一个的时候就是得到了结果。但是我们这里采用另一种思路，其时间复杂度是O（n），（好像有O（logn）的解法）。其思想基于递归，有点像动态规划的状态转移。参考圆圈中最后剩下的数字。关键找到前一个过程和后一个过程的映射关系。以及关系等式的化简。首先定一个关于最后剩下的数字的函数f（n,m），在这n个数字中，第一个被删除的数字是k=（m-1）%n，在剩下的序列中，K+1排在前面，剩下的数字也是有一个关于最后剩下的数字的函数f‘（n-1，m），f（n,m）== f‘（n-1，m），接下来就是把剩下的数字做一个映射，使得最后剩下的数字逆映射到原来的序列中（映射定义为P，逆映射定义为P’=（x+k+1）%n。，带入x、k之后，我们可以得到一个递归公式，看代码吧。

1
2
3
4
5
6
7
8
9
10
11
import sys
sys.setrecursionlimit(1000000)
class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n == 0:
            return -1
        elif n == 1:
            return 0
        else:
            return (self.LastRemaining_Solution(n-1,m)+m)%n

2.判断回文问题

题目：判断一个链表是否是回文结构

分析：回文问题可以借助额外的数据结构来求解，改进算法也是基于此。将链表按顺序输入到一个栈中，然后再一一弹出，并对照原来的链表上的值。

1
2
3
4
5
6
7
8
9
10
11
def is_palindrome_1(head):
    stack = []
    cur = head
    while cur is not None:
        stack.append(cur)
        cur = cur.next
    while stack:
        if stack.pop().val != head.val:
            return False
        head = head.next
    return True

3.逆序链表

题目：将一个链表逆序

分析：需要靠指针来进行逆序操作，一共有三个指针，pre、next以及head（这是指向当前位置的指针，因为不用head了，就直接使用head，一般是用另一个别名来替代）。算是模板，就是组件，其他算法可以靠这个逆序来进一步完成。

1
2
3
4
5
6
7
8
9
10
if not head or head.next == None:
	return head
pre = None
next = None
while head != None:
	head.next = pre # 改变next的方向
	next = head.next
	pre = head
	head = next # 调整指针的位置
return pre

4.链表环问题

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

分析：也是一个模板算法。在下一题中就有用到。这个算法分成三个部分，分别是找环中的某个点，计算环的长度，以及最后的找到环的入口节点。1.找环中的某点的思路就是用两个指针，一个慢指针，一个快指针。（慢指针走一步，快指针走两步）。当两个指针相遇时，一定是在环中的某个节点。2.计算环的长度就是直接标记一下第一步的那个节点，然后开始遍历，当再次遇到标记的节点时，走的步数就是环的长度。3.第三步则考虑从链表头节点开始走，绕过环一次后到达环入口的步数为m+n，m指的是从链表开头走到环入口一共走过的步数，n则是环的长度。我们让一个指针先走n步，然后再同步让另一个指针和这个指针一起走m步，当两个指针相遇时就是指向环入口的节点。

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
36
37
38
39
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        # 找到环，环如果不存在那就返回None
        def FindLoop(pHead):
            if not pHead:
                return None
            pHead1 = pHead
            pHead2 = pHead.next
            if pHead2 == None:
                return None
            while pHead1 and pHead2 and pHead1 != pHead2:
                pHead1 = pHead1.next
                pHead2 = pHead2.next
                if pHead2 == None:
                    return None
                else:
                    pHead2 = pHead2.next
            return pHead1
        # 计算环的长度
        def CountLoop(head):
            loopHead = head.next
            res = 1
            while loopHead != head:
                loopHead = loopHead.next
                res += 1
            return res
        loopNode = FindLoop(pHead)
        if not loopNode:
            return None
        # 找到环的入口
        loop_num = CountLoop(loopNode)
        pTmp = pHead
        for i in range(loop_num):
            pTmp = pTmp.next
        while pTmp != pHead:
            pTmp = pTmp.next
            pHead = pHead.next
        return pTmp

5.链表相交的问题

题目：请实现一个函数没如果两个链表相交，请返回相交的第一个节点；如果不相交，返回None。

分析：在剑指里面也有这一道题，但是在分析中没有提到链表是否存在环的问题，这里需要做一个补充。首先需要明确的一点是，两个相交的链表要嘛都是有环的，要嘛就都没有环。所以问题就变成了三个：

1.如何判断一个链表是否有环，如果有，则返回第一个进入环的节点。这里就是参考问题4；

2.如果链表无环，那如何判断链表是否相交？这里参考剑指，简单来说就是用两个链表的长度差来同步两个链表的遍历进度，然后看两个指针是否会相遇。

3.如果链表有环，如何判断链表是否相交？这个是新的问题。

​ （1）如果loop1 == loop2，那么两个链表的拓扑结构如下所示：

在这种情况下，有点类似问题二，只不过，这里把loop当做是两个链表的终点。

​ （2）如果loop1 ！= loop2，那么有两种情况：

让链表从loop1出发，如果在回到loop1之前遇到loop2，那么说明两个链表相交，返回loop1和loop2其中一个就行；如果没有遇到，那就说明两个链表不相交。

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
# 这里仅写第三种问题
def bothLoop(head1, node1, head2, node2):
    if head1 == None or head2 == None:
        return None
    if node1 == node2:
        cur1 = head1
        cur2 = head2
        n = 0
        # 这里将cur1作为比较长的链表的头，cur2作为较短的链表的头
        while cur1 != node1:
            n += 1
            cur1 = cur1.next
        while cur2 != node1:
            n -= 1
            cur2 = cur2.next
        cur1 = head1 if n >= 0 else head2
        cur2 = head1 if cur1 == head2 else head2
        n = abs(n)
        while n != 0:
            n -= 1
            cur1 = cur1.next
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        return cur1
    else:
        cur1 = node1.next
        while cur1 != node1:
            if cur1 == node2:
                return node1
            cur1 = cur1.next
        return None

6.将搜索二叉树转换成双向链表

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

分析：以根为中心的迭代算法，将根左边转换完成之后，连接到根(注意是左部分的最右边的节点连接到根），将根右边转换完成后也连接到根。若存在左边的部分，则返回指向左部分的第一个节点，否则返回根。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return None
        left = self.Convert(pRootOfTree.left)
        p = left
        while p and p.right:
            p = p.right
        if p:
            pRootOfTree.left = p
            p.right = pRootOfTree
        right = self.Convert(pRootOfTree.right)
        if right:
            pRootOfTree.right = right
            right.left =pRootOfTree
        return left if left else pRootOfTree
请作者喝杯咖啡吧！