七十、反转和合并链表、链表有环的判断

Python之王

共 3119字，需浏览 7分钟

· 2020-12-29

「@Author：Runsen」

❝
编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」
❞

最近在重新梳理学算法的知识，本文为链表常见操作复习的总结文章，会讲解常见的链表题目实现思路及附上答案，这些题目在leetcode上对应的题号也有给出，好好学习算法吧～

单链表反转
链表中环的检测
两个有序的链表合并
K个有序的链表合并

leetcode 对应题号：206，141，21，23

LeetCode 第 206 题：反转链表

反转一个单链表。

示例: 
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

题目不难，定义三个变量pre、cur、cur.next，分别记录上一个结点，当前结点、下一个结点。

反转一个单链表需要当前节点的next指针指向上一个结点pre，当前节点的指针指向下一个结点，上一个结点的指针指向当前节点。

通过迭代，依次反转结点指向。具体代码如下

class Solution:
    def reverseList(self, head):
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev

LeetCode 第 141 题：判断链表中是否有环

遍历整个数组, 给出的数据包含在集合中则说明有环, 返回 True; 若遍历完毕, 则说明无环, 返回 False，如果用列表也是一样。

「暴力解法」

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        """
        暴力法：通过遍历链表，用set来存储访问的节点，如果在set出现一样的节点，说明有坏，时间复杂度O(n)
        :type head: ListNode
        :rtype: bool
        """
        st = set()
        while head:
            if head in st:
                return True
            st.add(head)
            head = head.next
        return False


      # 下面是列表
        l = []
        while head:
            if head in l:
                return True
            else:
                l.append(head)
                head = head.next
        return False

从头遍历到尾，发现指向null，说明没环。这明显不靠谱。暴力的时间空间复杂度都是O(n)

题目要求用空间复杂度。其实，这道题考的是「快慢指针」 空间复杂度

通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

可以想象这样一个场景, 你和一个朋友一起散步, 你每次移动两步, 朋友每次一步, 如为单向定长道路, 你必然先到达重点. 若是环绕操场,则你们终将相遇.

class Solution(object):
    def hasCycle(self, head):
        slow = fast = head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

LeetCode 第21题：合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例： 

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

从两链表第一个结点开始比较结点的值，取较小者作为合并链表的元素，依次进行；后面如果有一个链表为空，则直接把不为空的链表接到合并链表的后面。

这个解决的方法使用递归，如果L1为空就返回L2，L2为空返回L1，L1的val<=L2的val，那么继续递归。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
 def mergeTwoLists(self, l1, l2):
  """
  :type l1: ListNode
  :type l2: ListNode
  :rtype: ListNode
  """
  #递归的结束点就是L1或者L2为空就返回
  #如果L1为空就返回L2，L2为空返回L1
  # if not (l1 and l2):
   # return l1 if l1 else l2
  if not l1:
            return l2
        elif not l2:
            return l1
  #L1的val<=L2的val，那么继续递归
  #当前L1的next指向一个递归函数
  #意思是L1的下一个和L2哪个大，就作为当前L1的next
   elif l1.val<=l2.val:
   l1.next = self.mergeTwoLists(l1.next,l2)
   return l1
  else:
   l2.next = self.mergeTwoLists(l1,l2.next)
   return l2

递归的代码看起来是十分简洁的

LeetCode 第 23 题：合并 k 个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例: 
输入:
[
 1->4->5,
 1->3->4,
 2->6
]
输出: 1->1->2->3->4->4->5->6

第一种法就是常规暴力思路，直接将所有的元素取出，然后排个序，再重组就达到了目的。

遍历所有链表，将所有节点的值放到一个数组中。将这个数组排序，然后遍历所有元素得到正确顺序的值。用遍历得到的值，创建一个新的有序链表。

时间复杂度：，其中 N 是节点的总数目

空间复杂度：。

排序花费空间（这取决于你选择的算法）。创建一个新的链表花费的空间。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode :
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next