leetcode刷题之链表必刷题（python实现）

深藏阁楼爱情的钟 2023-01-13 09:40 200阅读 0赞

最近重新回顾了一下链表，在自己手动写了链表的生成以及相应的增删查改操作后，对链表的理解更加深刻，于是在leetcode上刷了对应的习题。

王争老师列举了一些链表必刷题，感觉有必要做一下这些习题。

链表的必刷题有：

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第n个结点
  • 求链表的中间结点

文章目录

          1. [反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)
          • 递归实现：
          • 迭代实现
          1. [反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/)
        • 剑指 Offer 22. [链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)
          • 使用快慢指针
          • 先遍历再取节点
          1. [删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
          1. [链表的中间结点](https://leetcode-cn.com/problems/middle-of-the-linked-list/)
          • 快慢指针法
          • 先遍历再求节点
          1. [合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
          1. [环形链表](https://leetcode-cn.com/problems/linked-list-cycle/)
          1. [环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)

206. 反转链表

在这里插入图片描述

这道题可以用迭代或者递归实现。

递归和迭代的思路都是不断反转两个节点。

递归实现：
  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. # def __init__(self, val=0, next=None):
  4. # self.val = val
  5. # self.next = next
  6. class Solution(object):
  7.     def reverseList(self, head):
  8.         """ :type head: ListNode :rtype: ListNode """
  9.         # 有一个节点或者没有节点时，直接返回列表
  10.         if not head or not head.next:
  11.             return head
  13.         pre, node = head, head.next
  14.         while node:
  15.             pre, node = self.__reverse_two(pre, node)
  17.         head.next = None
  18.         head = pre
  19.         return head
  21.     def __reverse_two(self, pre, node):
  22.         # 反转两个节点
  23.         tmp = node.next
  24.         node.next = pre
  25.         pre, node = node, tmp
  26.         return pre, node
迭代实现
  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. # def __init__(self, val=0, next=None):
  4. # self.val = val
  5. # self.next = next
  6. class Solution(object):
  7.     def reverseList(self, head):
  8.         """ :type head: ListNode :rtype: ListNode """
  9.         if not head or not head.next:
  10.             return head
  11.         pre, node = head, head.next
  12.         while node:
  13.             temp = node.next
  14.             node.next = pre
  15.             pre = node
  16.             node = temp
  18.         head.next = None
  19.         return pre

92. 反转链表 II

在这里插入图片描述

反转链表92的题目可以在反转链表206的题目上修改。

反转的逻辑可以复用。

这里主要是要找到反转的起始节点和终止节点，同时要保存剩下的节点。

  1. # Definition for singly-linked list.
  2. # class ListNode(object):
  3. # def __init__(self, val=0, next=None):
  4. # self.val = val
  5. # self.next = next
  6. class Solution(object):
  7.     def reverseBetween(self, head, left, right):
  8.         """ :type head: ListNode :type left: int :type right: int :rtype: ListNode """
  9.         if not head.next:
  10.             return head
  12.         fake_head = ListNode(-1)
  13.         fake_head.next = head
  14.         pre = fake_head
  15.         # 得到反转起始节点的前向节点
  16.         for i in range(left - 1):
  17.             pre = pre.next
  19.         reverse_end = pre
  20.         # 得到反转终止节点
  21.         for i in range(right - left + 1):
  22.             reverse_end = reverse_end.next
  24.         # 剩余不反转的节点
  25.         end_node = reverse_end.next
  26.         # 反转起始节点
  27.         reverse_start = pre.next
  28.         # 反转终止节点指向None， 反转起始节点的前向节点指向None
  29.         reverse_end.next = None
  30.         pre.next = None
  32.         # 反转中间部分的节点
  33.         # 反转起始节点reverse_start, 终止是 reverse_end
  34.         pre_, node_ = reverse_start, reverse_start.next
  35.         while node_:
  36.             pre_, node_ = self.__reverse(pre_, node_)
  38.         pre.next = pre_
  39.         reverse_start.next = end_node
  40.         return fake_head.next
  42.     # 利用递归反转，也可以使用迭代
  43.     def __reverse(self, pre, node):
  44.         tmp = node.next
  45.         node.next = pre
  46.         pre, node = node, tmp
  47.         return pre, node

剑指 Offer 22. 链表中倒数第k个节点

在这里插入图片描述

求倒数第k个节点有两种方法，第一种是使用快慢指针，第二种就是先求出链表的长度，再遍历得到对应节点

使用快慢指针

使用快慢指针可以只扫描一次。

  1. # class ListNode(object):
  2. # def __init__(self, x):
  3. # self.val = x
  4. # self.next = None
  6. class Solution(object):
  7.     def getKthFromEnd(self, head, k):
  8.         """ :type head: ListNode :type k: int :rtype: ListNode """
  9.         if not head or not head.next:
  10.             return head
  12.         fast = slow = head
  13.         # 快指针先走k步
  14.         for i in range(k):
  15.             fast = fast.next
  16.         while fast:
  17.             slow = slow.next
  18.             fast = fast.next
  19.         # 当快指针走完的时候，慢指针就位于该节点
  20.         return slow
先遍历再取节点
  1. # class ListNode(object):
  2. # def __init__(self, x):
  3. # self.val = x
  4. # self.next = None
  6. class Solution(object):
  7.     def getKthFromEnd(self, head, k):
  8.         """ :type head: ListNode :type k: int :rtype: ListNode """
  9.         if not head or not head.next:
  10.             return head
  12.         # 先求出链表长度
  13.         n = 0
  14.         p = head
  15.         while p:
  16.             p = p.next
  17.             n += 1
  19.         # 遍历找到k的位置
  20.         pos = 0
  21.         p = head
  22.         while p and k != (n - pos):
  23.             p = p.next
  24.             pos += 1
  25.         return p

19. 删除链表的倒数第 N 个结点

在这里插入图片描述

删除倒数第n个节点也可以使用快慢指针的思路。

  1. # class ListNode(object):
  2. # def __init__(self, val=0, next=None):
  3. # self.val = val
  4. # self.next = next
  5. class Solution(object):
  6.     def removeNthFromEnd(self, head, n):
  7.         """ :type head: ListNode :type n: int :rtype: ListNode """
  8.         # 没有节点或者只有一个节点时直接返回
  9.         if not head or not head.next:
  10.             return head
  12.         fast = slow = head
  13.         # 快指针先走n步
  14.         for i in range(n):
  15.             fast = fast.next
  17.         # pre指针用于找到倒数第n个节点的前向节点
  18.         pre = ListNode(-1)
  19.         while fast:
  20.             pre.next = slow
  21.             slow = slow.next
  22.             fast = fast.next
  23.             pre = pre.next
  25.         pre.next = slow.next
  26.         return head

876. 链表的中间结点

在这里插入图片描述

采用的方法是先求链表长度，再求中间节点。或者快慢指针。
感觉这道题和求倒数第n节点的思想都差不多

快慢指针法

快指针比慢指针多走两步，当快指针走完时，慢指针指向的节点就是中间节点

  1. # class ListNode(object):
  2. # def __init__(self, x):
  3. # self.val = x
  4. # self.next = None
  6. class Solution(object):
  7.     def middleNode(self, head):
  8.         """ :type head: ListNode :rtype: ListNode """
  9.         slow = fast = head
  10.         while fast and fast.next:
  11.             slow = slow.next
  12.             fast = fast.next.next
  13.         return slow
先遍历再求节点
  1. # class ListNode(object):
  2. # def __init__(self, x):
  3. # self.val = x
  4. # self.next = None
  6. class Solution(object):
  7.     def middleNode(self, head):
  8.         """ :type head: ListNode :rtype: ListNode """
  9.         n = 0
  10.         p = head
  11.         while p:
  12.             p = p.next
  13.             n += 1
  15.         mid = n // 2
  16.         p = head
  17.         pos = 0
  18.         while p and pos != mid:
  19.             p = p.next
  20.             pos += 1
  21.         return p

21. 合并两个有序链表

在这里插入图片描述

两个链表分别用指针遍历

  1. # class ListNode(object):
  2. # def __init__(self, val=0, next=None):
  3. # self.val = val
  4. # self.next = next
  5. class Solution(object):
  6.     def mergeTwoLists(self, l1, l2):
  7.         """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """
  8.         fake_head = ListNode(-1)
  9.         pre = fake_head
  10.         while l1 and l2:
  11.             if l1.val <= l2.val:
  12.                 pre.next = l1
  13.                 l1 = l1.next
  14.             else:
  15.                 pre.next = l2
  16.                 l2 = l2.next
  17.             pre = pre.next  # 写代码的时候遗漏了该指针的移动
  18.         # 剩余节点
  19.         pre.next = l1 or l2
  20.         return fake_head.next

141. 环形链表

在这里插入图片描述

这道题也是使用快慢指针，如果有环，快慢指针最终相遇。

快指针始终比慢指针多走一步

  1. # class ListNode(object):
  2. # def __init__(self, x):
  3. # self.val = x
  4. # self.next = None
  6. class Solution(object):
  7.     def hasCycle(self, head):
  8.         """ :type head: ListNode :rtype: bool """
  9.         # 加上这个判断之后时间更快了
  10.         if not head or not head.next:
  11.             return False
  13.         fast = slow = head
  14.         while fast and fast.next:
  15.             slow = slow.next
  16.             fast = fast.next.next
  17.             # 快慢指针相遇说明存在环
  18.             if slow == fast:
  19.                 return True
  20.         return False

142. 环形链表 II

在这里插入图片描述

这道题也使用快慢指针，只不过还需要看相遇的节点是第几个节点。

  1. # class ListNode(object):
  2. # def __init__(self, x):
  3. # self.val = x
  4. # self.next = None
  6. class Solution(object):
  7.     def detectCycle(self, head):
  8.         """ :type head: ListNode :rtype: ListNode """
  9.         if not head or not head.next:
  10.             return None
  12.         fast = slow = head
  13.         while fast and fast.next:
  14.             slow = slow.next
  15.             fast = fast.next.next
  16.             if slow == fast:
  17.                 pre = head
  18.                 while pre != slow:
  19.                     pre = pre.next
  20.                     slow = slow.next
  21.                 return pre
  22.         return None

发表评论

表情：
评论列表 （有 0 条评论，200人围观）

还没有评论，来说两句吧...

相关阅读