链表练习题

# 练习题

# 1.删除链表的倒数第 N 个结点 (opens new window)

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

1
2

笔记

方法一：找到要删除的前驱节点，直接删除，注意处理第一个节点，认为添加一个头节点


class Solution:
  def removeNthFromEnd(self, head, n: int):
      """
      倒数第n个节点，也就是删除正向的第len-n +1 个节点
      链表是没有len 方法的，需要先找到链表的长度
      为了让第一个节点能操作一致， 添加一个头节点
      new-head.next 为真正的头节点
      """

      dummary = ListNode(0, head)
      length = 0
      while head:
          head = head.next
          length += 1
      cur = dummary
      for i in range(1, length - n +1):
          cur = cur.next
      cur.next = cur.next.next
      return dummary.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

笔记

方法二：借助栈的特性


class Solution:
  def removeNthFromEnd(self, head, n: int):
  	"""
  	利用找的特性
  	则出栈找到要删除前N个节点，出栈
  	此时，stack[-1] 即栈顶就是要删除的前驱节点
  	找到前驱节点后，根据链表的删除方法，删除节点就可以了
  	"""
      # 方法二， 借助栈
      dummy = ListNode(0, head)
      stack = list()
      cur = dummy
      while cur:
          stack.append(cur)
          cur = cur.next
      
      for i in range(n):
          stack.pop()
      
      # 前驱节点
      prev_node = stack[-1]

      prev_node.next = prev_node.next.next
      return dummy.next

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

// Make sure to add code blocks to your code group

# 2.两两交换链表中的节点 (opens new window)

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def swapPairs(self, head):
      
      dummy = ListNode(0, head)
      cur = dummy
      while cur.next and cur.next.next:
          node1 = cur.next
          node2 = cur.next.next
          cur.next = node2
          node1.next = node2.next
          node2.next = node1
          cur = node1
      return dummy.next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// Make sure to add code blocks to your code group

# 3. K 个一组翻转链表（需补充解题方法） (opens new window)

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

// Make sure to add code blocks to your code group

# 4.环形链表 (opens new window)

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。否则，返回 false 。

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

class Solution:
  # 哈希set的方式
  def hasCycle(self, head: Optional[ListNode]) -> bool:
      viewed = set()

      while head:
          if head in viewed:
              return True
          viewed.add(head)
          head = head.next
      return False
  
  
  # 快慢指针
  def hasCycle(self, head: Optional[ListNode]) -> bool:
      if not head:
          return False
      slow = fast = head
      while fast.next and fast.next.next:
          slow = slow.next
          fast = fast.next.next
          if slow is fast:
              return True
      return False

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

// Make sure to add code blocks to your code group

# 5. 环形链表 II (opens new window)

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

:: note

数学推导+ 快慢指针

设链表的总长度为a+b ，其中a为头节点到入口处的距离，b为环形的长度

现在假设有两个人开始跑步，一个人的速度是另一个人的两倍，他们们在相遇点相遇，此时我们看看他们走过的距离关系

第一次相遇

令slow的走过的距离为slow = s --->fast = 2s
由于是在环内相遇，可知fast一定是套圈slow了，且快的人比慢的人在圈里多跑了n圈，即nb, 由于慢的人走了s，所有快的人走了fast = s + nb (具体n是几未知)
有1式减2可得s = nb
可以再看，每次经过入口点得距离k = a + nb
由于s已经搜了nb步，所以只需要再走a步就是入口点，如何得到a步呢

第二次相遇

1. 由上面推导我们可得slow 再走a步就是入口点，
1. 此时让快得人去起始点，保持和慢得人一致得速度，当两人相遇时，恰好走了a步

1
2

:::

class Solution:
  
  def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
      fast = slow = head
      if not head:
          return None
      while fast.next and fast.next.next:
          fast = fast.next.next  # 走两步
          slow = slow.next
          if fast is slow:  # 首次相遇:
              fast = head
              while fast is not slow:
                  fast = fast.next
                  slow = slow.next
                  #if fast is slow:
                  #    return slow
              return fast
      return None

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Make sure to add code blocks to your code group

# 6. 相交链表 (opens new window)

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须保持其原始结构。

自定义评测：

评测系统的输入如下（你设计的程序不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

笔记

采用hash 表的方式，看是否存在hash表中

class Solution:
  def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:

      viewed = set()

      while headA:
          viewed.add(headA)
          headA = headA.next
      while headB:
          if headB in viewed:
              return headB
          headB = headB.next
      return None

1
2
3
4
5
6
7
8
9
10
11
12
13

// Make sure to add code blocks to your code group

# 7. 重排链表 (opens new window)

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln 请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

笔记

方法一：栈+ 计算中间节点得前驱节点+链表原地插入

class Solution(object):
  def reorderList(self, head):
      """
      :type head: ListNode
      :rtype: None Do not return anything, modify head in-place instead.
      """
      if not head: return None        
      stack = []
      cur = head
      while cur:
          stack.append(cur)
          cur = cur.next

      n = len(stack)

      middle = (n-1) //2
      cur = head
      while middle:
          tmp = stack.pop()

          # 将栈中得元素插入到head中
          tmp.next = cur.next
          cur.next = tmp
          cur = cur.next.next
          middle -= 1
      stack.pop().next = None

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

笔记

方法二：反转链表 + 链表中点 + 链表拼接

class Solution(object):
  def reorderList(self, head):
      """
      :type head: ListNode
      :rtype: None Do not return anything, modify head in-place instead.
      """
      if not head or not head.next:
          return head
      def middle_node(head):
          slow = fast = head
          while fast.next and fast.next.next:
              slow = slow.next
              fast = fast.next.next
          return slow

      def reverse_link(head):
          """
          原地逆置法
          初始化两个三个指针，一个指向头节点，一个指向第一个节点，一个指向第二个节点
          """
          beg= head
          end = head.next
          while end:
              beg.next = end.next
              end.next = head
              head = end
              end = beg.next
          return head

      def mergeList(l1, l2):
          while l1 and l2:
              l1_next = l1.next
              l2_next = l2.next

              l1.next = l2
              l1 = l1_next

              l2.next = l1
              l2 = l2_next

      node = middle_node(head)
      right = node.next #右半部链表
      node.next = None  # 注意一定要断链

      # 逆置链表
      right = reverse_link(right)
      # 合并两个链表
      mergeList(head, right)

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
40
41
42
43
44
45
46
47
48

// Make sure to add code blocks to your code group

# 8. 链表的中间结点 (opens new window)

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

// Make sure to add code blocks to your code group

# 9.常见反转链表的方法

# 9.1.头插法

所谓头插法，是指在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版

新建一个头指针指向空的节点
将原链表的节点插入新节点的头部
重复上面操作，每次插入头部，这样最终就实现了逆置

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

      """
      头插法
      原地逆置法
      """
      new_head = None
      while head:
          next = head.next
          head.next = new_head
          new_head = head
          head = next
      return new_head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// Make sure to add code blocks to your code group

# 9.2.原地逆置法

头插法需要建立新的链表，而原地逆置法是在原来链表的基础上直接进行修改。此时需要借助两个指针

初始状态下， head 指向头节点， beg指向第一个节点，end 指向第二个节点
第一轮交换，将end 节点摘出来，然后添加至链表的头部
将end指向bed.next节点，然后将end指向的节点从链表中摘除，然后将end节点添加至头部
依次重复最后完成反转链表

笔记

注意边界条件以及初始化beg和end指针

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

      """
      原地逆置法
      """
      if not head or not head.next:
          return head
      # 初始化两个指针
      beg = head
      end = head.next
      while end:
          #beg = head
          #end = head.next
          beg.next = end.next
          end.next = head
          head = end
          end = beg.next
      return 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

// Make sure to add code blocks to your code group

编辑

上次更新: 2024/12/31 14:23:38

← 基本认知基本认知→