链表问题汇总

1 前言
2 题目
- 2.1 链表中倒数第k个结点
- - 2.1.1 题目
  - 2.1.2 思路
  - 2.1.3 代码
- 2.2 反转链表
- - 2.2.1 题目
  - 2.2.2 思路
  - 2.2.3 代码
- 2.3 合并两个排序的链表
- - 2.3.1 题目
  - 2.3.2 思路1
  - 2.3.3 代码1
  - 2.3.4 思路2
  - 2.3.5 代码2
- 2.4 两个链表的第一个公共结点
- - 2.4.1 题目
  - 2.4.2 思路
  - 2.4.3 代码
  - 2.4.4 图解
- 2.5 复杂链表的复制
- - 2.5.1 题目
  - 2.5.2 思路
  - 2.5.3 图解
  - 2.5.4 代码
- 2.6 链表中环的入口结点
- - 2.6.1 题目
  - 2.6.2 思路
  - 2.6.3 图解
  - 2.6.4 代码
- 2.7 删除链表中重复的结点
- - 2.7.1 题目
  - 2.7.2 思路1
  - 2.7.3 代码1
  - 2.7.4 思路2
  - 2.7.5 代码2
参考

1 前言

整理下剑指offer链表问题。

2 题目

2.1 链表中倒数第k个结点

2.1.1 题目

输入一个链表，输出该链表中倒数第k个结点。

2.1.2 思路

思路：

如果输出链表正向的第k个结点会吗？应该会的！那么再得到长度，一减，就ok了啊！
但是上面思路太麻烦，有一个非常牛逼的思路！
牛逼思路：我们可以定义两个指针。
- 第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；
- 从第k步开始，第二个指针也开始从链表的头指针开始遍历。
- 由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
图示：

剑指offer | 链表问题汇总1 前言2 题目参考

2.1.3 代码

代码写起来！
写代码发现有报错，考虑下边界条件：如果查询的是最后一个元素咋办？也就是倒数第一个！

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        fast = slow = head
        '''
        为什么这种思路ok？
		因为是循环k次，也就是距离为k 这时候就不能以.next作为循环终止条件了！而是自己为终止条件！但还是下面一种好思考一些！
        '''
        for _ in range(k):
            if not fast: # 如果fast为空 返回空 
                return None
            fast = fast.next
        while fast:
            slow, fast = slow.next, fast.next
        return slow

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        # 边界条件！
        if head == None or k == 0:
            return None
        # 初始化指针
        phead = head
        pbehind = head
        # 先走k-1步
        for i in range(k-1):
            if phead.next == None: # 防止出现链表就1个元素 然后说倒数第二个元素 这样就gg
                return None
            else:
                phead = phead.next
        while phead.next != None: # 只要走在前面的指针的下一步不是指向None 那么就继续移动！
            phead = phead.next
            pbehind = pbehind.next
        return pbehind

注意return的结果！！！不要把元素搞出来！看题目的需求！！！是返回节点！！！现在直接返回节点就ok！所以审题相当重要！

2.2 反转链表

2.2.1 题目

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

2.2.2 思路

思路：

如何反转呢？也就是把元素全部倒置过来！如何实现？
能不能依次存储到一个list 然后反转list？好像不太行吧？因为最后要输出表头诶？就是直接输出一个节点！
我好像只要找到新链表的表头就ok了？所以不需要存储？那直接遍历到最后一个输出？不行的！输出就是反转的链表！

剑指offer | 链表问题汇总1 前言2 题目参考

代码思路：

每一步解释下面都有！
值得注意的就是最后返回的是pre！
一开始pre的定义是None！因为首节点反转之后要指向None！巧妙！
循环体部分包括两部分：
- 转换节点方向【先保存下一个指向信息再转向】
- 移动指针【直接前一个指向后一个后一个指向之前保存的next！】
注意考虑特殊情况
- 空链表
- 只有1个节点的链表的情形！

2.2.3 代码

代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead == None:
            return None
        # 定义两个指针
        pre = None #前一个节点 因为头节点反转后需要指向None
        cur = pHead # 当前节点
        # 开始循环
        while cur != None:
            # 先保留当前节点的下一个信息 防止链表断裂
            next = cur.next
            # 让当前节点指向前一个节点
            cur.next = pre
            # 移动指针
            pre = cur
            cur = next
        return pre

2.3 合并两个排序的链表

2.3.1 题目

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

2.3.2 思路1

思路：

如何合并呢？两个排序的链表？是否要比较链表内元素的大小？关键应该还是指向的问题！
如果逐个元素两两比较是不是太麻烦了？应该有其余的方法！在两个链表上分别设指针？思路没问题！但是稍微修改下！

代码思路：

非递归版本
一开始先定义一个空的节点！然后让pHead指向它！这样就能很好地解决最后不知道返回谁的问题！直接返回pHead.next 逐个打印出来就行了！
中间的判断循环语句和自己一开始的思路一致不难！谁元素小指向谁！并且它还要移动！
最后需要做一个判断的就是有可能一个链表中元素为空了！那么这时候全部指向另一个就ok！
中间有一个细节就是 tmp = tmp.next 具体原因上面解释了！
最后返回的是 pHead.next 记住这个trick！

2.3.3 代码1

非递归版本代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        # 先考虑特殊情况
        #初始化
        tmp = ListNode(0)
        pHead = tmp # pHead指向tmp
        # 开始循环
        while pHead1 and pHead2: # 均非空
            if pHead1.val < pHead2.val: # 如果1的元素小于2的 改变1
                tmp.next = pHead1 # 让初始tmp指向1
                pHead1 = pHead1.next # 移动1
            else: # 如果1的元素大于2的 改变2
                tmp.next = pHead2 # 让初始tmp指向2
                pHead2 = pHead2.next # 移动2
            tmp = tmp.next # 同时tmp每一次循环结束后都要向前移动一次！因为之后都要指向新元素 所以要移动到目前的位置！
        # 循环结束 看哪一个为空
        if not pHead1: # 如果pHead1为空 那么tmp直接下一步指向2
            tmp.next = pHead2
        if not pHead2: # 如果pHead2为空 那么tmp直接下一步指向1
            tmp.next = pHead1
        return pHead.next # 最后返回谁呢？为什么返回pHead.next？可以一个一个的打印出来！

2.3.4 思路2

递归版本图解：

剑指offer | 链表问题汇总1 前言2 题目参考

2.3.5 代码2

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        # 先考虑特殊情况
        if pHead1 is None:
            return pHead2
        if pHead2 is None:
            return pHead1
        # 开始循环递归判断！
        if pHead1.val < pHead2.val: # 1元素小于2 
            pHead1.next = self.Merge(pHead1.next,pHead2) # 让1指向除了1+2的新的两个链表 
            return pHead1 # 最后返回pHead1？妙！
        else:
            pHead2.next = self.Merge(pHead1,pHead2.next)
            return pHead2

代码思路：

这个递归版本思路太妙了！
怎么想呢？就是说每次比较两个元素之后，不局限于元素之间的指向转变！而是直接将小的元素指向一个新的两个链表！递归实现！

以[1 3 ] [2 4 ] 来示例：

进入循环：

pHead1.next = self.Merge(pHead1.next,pHead2)=[3,5],[2,4,6]
					= 进入第二个循环

pHead2.next = self.Merge(pHead1,pHead2.next)=[3,5],[4,6]
           = 进入第一个循环

pHead1.next = self.Merge(pHead1.next,pHead2)=[5],[4,6]
					= 进入第二个循环

pHead2.next = self.Merge(pHead1,pHead2.next)=[5],[6]
           = 进入第一个循环

pHead1.next = self.Merge(pHead1,pHead2.next)=[None],[6]
           	= 6

直接从图形角度理解吧！逆推推不回去！就想着每次会多出一个元素出来！
return 1 还是 2 取决于第一次进入的是哪个部分里面！不要过多纠结于每一步的细节！从图形角度理解就ok！

2.4 两个链表的第一个公共结点

2.4.1 题目

输入两个链表，找出它们的第一个公共结点。

2.4.2 思路

思路：

直接搜索！要不要先排序呢？然后二分查找？但是排序的复杂度会比较高吧？是的！
先暴力搜索！先固定一个链表的一个元素，然后遍历另外一个链表，再换另一个元素！

写了代码，但是测试用例有点一脸懵逼，

剑指offer | 链表问题汇总1 前言2 题目参考

测试用例说明这个题目的意思是公共节点之后的元素都一样！

a = {1,2,3,6,7}

b = {4,5,6,7}

图解就是：

剑指offer | 链表问题汇总1 前言2 题目参考

这时候采用一种思路：

先让把长的链表的头砍掉，让两个链表长度相同，这样，同时遍历也能找到公共结点。此时，时间复杂度O(m+n)，空间复杂度为O(MAX(m,n))。

2.4.3 代码

代码为：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        # 下面这个没问题 先判断特殊情况
        if pHead1 == None or pHead2 == None:
            return None
        cur1, cur2 = pHead1, pHead2
        while cur1 != cur2:
            cur1 = cur1.next if cur1 != None else pHead2
            cur2 = cur2.next if cur2 != None else pHead1
        return cur1

这种做法代码看起来其实有点炫，我们来分解一下，如何让两个长度不同的链表并驾齐驱的？

2.4.4 图解

其实四张图就可以解释！图解如下：

剑指offer | 链表问题汇总1 前言2 题目参考

2.5 复杂链表的复制

2.5.1 题目

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

2.5.2 思路

思路：

完全没有思路，啥意思？复制链表？咋复制？而且这个链表还很奇怪，两个指向，一个是下一个节点，一个是任意一个节点？蜜汁操作！什么叫复制？以及返回head头结点？

思路还是比较6的：

我们这里将复杂链表的复制过程分解为三个步骤。在写代码的时候我们每一步定义一个函数，这样每个函数完成一个功能，整个过程的逻辑也就非常清晰明了了。

我们这里采用三步：

第一步：复制复杂指针的label和next。但是这次我们把复制的结点跟在元结点后面，而不是直接创建新的链表；
第二步：设置复制出来的结点的random。因为新旧结点是前后对应关系，所以也是一步就能找到random；
第三步：拆分链表。奇数是原链表，偶数是复制的链表。

2.5.3 图解

图解为：

剑指offer | 链表问题汇总1 前言2 题目参考

2.5.4 代码

代码为：

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        
        # 边界条件：如果为空链表 返回空
        if not pHead:
            return None
        
        # 首先定义一个指针
        dummy = pHead
        
        # first step, N' to N next 即 复制链表 紧跟它后面！
        while dummy: # 爸爸非空即进入循环
            # 1 记录爸爸的next指向
            dummynext = dummy.next
            # 2 记录爸爸基因（label），产生儿子
            copynode = RandomListNode(dummy.label)
            # 3 让儿子指向爸爸的next指向
            copynode.next = dummynext
            # 4 让爸爸指向儿子
            dummy.next = copynode
            # 5 让爸爸继续向前 指向本应该的next
            dummy = dummynext
        
        # 复制完成 重新归一化dummy
        dummy = pHead
         
        # second step, random' to random' 即确定random的指向
        while dummy:
            # 1 先记录父亲的random位置
            dummyrandom = dummy.random
            # 2 让儿子指向爸爸的next位置
            copynode = dummy.next
            # 3 如果存在父亲的random位置就让儿子的random也复制一下
            if dummyrandom:
                copynode.random = dummyrandom.next
            # 4 重点：如何让父亲继续走？让父亲指向儿子的next节点即可！
            dummy = copynode.next
        
        # third step, split linked list 分开list 奇数为真实 偶数为复制的！即如何返回copynode
        # 其实就是确定新的指向！新的链表指向顺序！
        # 复制random完成 重新归一化dummy
        dummy = pHead
        # 爸爸的next指向儿子头结点copyHead！
        copyHead = pHead.next  
        while dummy:
            # 只要爸爸不为空 进入循环！
            # 1 产生儿子-爸爸dummy的next
            copyNode = dummy.next
            # 2 dummynext记录爸爸实际的next指向-copyNode.next
            dummynext = copyNode.next
            # 3 让爸爸跳到实际的next指向上
            dummy.next = dummynext
            # 4 如果dummynext非空 那么儿子的下一个指向为dummynext的next指向
            if dummynext:
                copyNode.next = dummynext.next
            else:
                copyNode.next = None
            # 5 让父亲指向实际的下一个位置 继续循环！
            dummy = dummynext
        return copyHead

2.6 链表中环的入口结点

2.6.1 题目

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

2.6.2 思路

思路：

遍历链表！
什么情况下会包括环呢？也就是某一个节点的next指向前面的任一节点！这时候输出该节点？
如何判断某一个节点的next指向前面的任一节点？其实指向后面的节点也ok！就是不指向下一个！如何判断呢？好难啊！不好想~

牛逼的思路：

分为两部分。一个结论+如何确定链表环中元素的个数！
结论：如果一个链表有环，且环中元素的个数为n，那么定义两个指针，一个指针先走n步，另一个指针在原点位置，然后同时开始移动两个指针，直至两个指针相遇，相遇的元素即为环的入口节点！

2.6.3 图解

具体见下图：

剑指offer | 链表问题汇总1 前言2 题目参考

如何确定环内元素的个数呢？使用**快慢指针**！定义两个指针，一前一后，一个移动2步，一个移动1步，两个指针肯定会相遇，具体见下图：

剑指offer | 链表问题汇总1 前言2 题目参考
相遇之后只使用一个指针开始继续向前走，一直到又走到这个位置的时候，记录下走了多少次，即为环内元素个数！
如果判断没有环呢？如何判断？那就是快慢指针的时候没有相遇！此时就没有环了！

2.6.4 代码

下面开始写代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        if not pHead:
            return None
       
        # 1 首先定义快慢指针 确定是否有环以及环内元素个数
        # 1.1 定义指针 注意一开始要选择不同的
        slow = pHead
        fast = pHead.next
        # 1.2 快慢指针开始遍历 直至相遇
        while slow != fast:
        	# 注意考虑边界情况！就是只有一个节点！肯定也不会有环！
            if slow.next == None or fast.next == None:
                return None
            else:
            	# 慢指针一次走一步 快指针一次两步
                slow = slow.next
                fast = fast.next.next
        # 1.3 相遇 用一个指针去走 直至回来
        tmp = slow
        n = 1
        while tmp.next !=  slow:
            n += 1
            tmp = tmp.next
        # 1.4 确定了环内元素个数 
		
		# 2 再定义两个指针！确定入口结点
		# 2.1 定义两个指针
        cur1 = pHead
        cur2 = pHead
        # 2.2 先移动cur2往前n步
        for i in range(n):
            cur2 = cur2.next
        # 2.3 现在开始同步移动 直至两者相等
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        return cur1

2.7 删除链表中重复的结点

2.7.1 题目

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

2.7.2 思路1

这个思路超牛逼！

先将每个元素过一遍！然后统计出现的次数！过滤掉元素大于1的！
然后再将剩余的元素组织成链表的形式！
完美！

2.7.3 代码1

思路比较清晰！开始写代码：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        res=[]
        while pHead:
            res.append(pHead.val)
            pHead=pHead.next
        res=list(filter(lambda c:res.count(c)==1,res))
        
        newList=ListNode(0)
        pre=newList
        for i in res:
            node=ListNode(i)
            pre.next=node
            pre=pre.next
        return newList.next

2.7.4 思路2

思路：

已经排序了，那就直接遍历每一个元素吧！如果遇到相同的，都删了关键就是得确定指向的问题！所以应该至少要有2个指针！保留重复元素的最后一个元素的next指向，让首个重复元素前面元素指向该next指向即可！遇到重复的就一直往下走！直到不等于！while！

思路更新：

其实思路和自己想的基本差不多只不过有些细节需要注意
首先得创建一个first，作为最初始！其指向head！
定义一个指针跟着pHead跑！因为要考虑其前面的元素！！！！
进入循环直接考虑两个元素是否相等，相等取出元素来进行遍历循环，然后让之前的前一个指针指向它，即在判断的时候只用自身以及next来判断就好！保持前指针last的纯粹性！
最后返回是谁也很重要！为什么不返回pHead？因为第一个元素无法显示！没有指向第一个元素的！而pHead是最后一个。为什么不返回last，因为没有指向第一个元素！只有first符合条件！

2.7.5 代码2

代码2：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        # 特殊情况
        if not pHead:
            return None
        # 得定义一个指针跟着pHead跑！因为要考虑其前面的元素！
        first=ListNode(-1)
        first.next=pHead
        last=first
        
        while pHead and pHead.next:
            # 开始一次判断
            if pHead.val == pHead.next.val:
                # 如果两个元素相等 则往后继续移动-取出值来 做判断依据
                val = pHead.val
                while pHead and pHead.val == val:
                    pHead = pHead.next
                # 循环结束 说明此时跳出了重复元素 改变指向
                last.next = pHead
            else:
                # 说明元素不等 继续往前移动
                last = pHead
                pHead = pHead.next
        return first.next

参考

https://blog.csdn.net/c406495762/article/details/79247243

剑指offer | 链表问题汇总1 前言2 题目参考

链表问题汇总

1 前言

2 题目

2.1 链表中倒数第k个结点

2.1.1 题目

2.1.2 思路

2.1.3 代码

2.2 反转链表

2.2.1 题目

2.2.2 思路

2.2.3 代码

2.3 合并两个排序的链表

2.3.1 题目

2.3.2 思路1

2.3.3 代码1

2.3.4 思路2

2.3.5 代码2

2.4 两个链表的第一个公共结点

2.4.1 题目

2.4.2 思路

2.4.3 代码

2.4.4 图解

2.5 复杂链表的复制

2.5.1 题目

2.5.2 思路

2.5.3 图解

2.5.4 代码

2.6 链表中环的入口结点

2.6.1 题目

2.6.2 思路

2.6.3 图解

2.6.4 代码

2.7 删除链表中重复的结点

2.7.1 题目

2.7.2 思路1

2.7.3 代码1

2.7.4 思路2

2.7.5 代码2

参考

继续阅读