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

发表于： 分类于：
字数：375 阅读：≈ 1分钟 浏览：

删除链表的倒数第N个节点-使用双节点解题

题目描述

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

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
  • 示例2：
输入：head = [1], n = 1
输出：[]
  • 示例3：
输入：head = [1,2], n = 1
输出：[1]
  • 提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

代码

  • 普通思路代码
 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

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
   def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
       h1 = ListNode(next=head)
       cur = h1.next
       cnt = 0
       tail = None

       while cur!= None:
           cur = cur.next
           cnt +=1
       
       k = cnt - n
       
       tmp = h1
       for i in range(0,k):
           tmp = tmp.next
       
       if tmp.next != None:
           tmp.next = tmp.next.next

       return h1.next
  • 进阶【使用一遍遍历解决，双指针方法】
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

# @lc code=start
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
   def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
       h1 = ListNode(next=head)
       q = h1
       s = h1
       hh = h1.next
       for i in range(0,n):
           q=q.next

       while q.next != None :
           s = s.next
           q = q.next

       s.next = s.next.next

       return h1.next