leetcode (力扣) 19. 删除链表的倒数第 N 个结点

凌凌漆 lv.2

发布时间：2022-11-01 08:14:00 336

法一:

1.先找到整个链表的长度。
2.算出需要从头开始移动的步数。
3.删除对应的节点。

比如:链表为:head = [1,2,3,4,5], 需要删除倒数第2个节点。n = 2。

首先我们定义一个指针p开始遍历链表，同时使用time记录链表长度。
删除倒数第二个节点就是 4 。计算从头走需要多少步才能达到需要删除的节点，显然是 time-n = 5-2 = 3步，但是既然要在链表里删除节点，我们可以直接到达要删除的前一个节点，这样就比较方便删除。
在计算的过程中需要注意，如果我们time-n-1 = -1 则说明要删除的是第一个节点，这时候直接return head.next即可

完整代码

# 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: ListNode, n: int) -> ListNode:
        if not head.next:
            return None
        time = 0
        p = head
        while p: # 找出链表长度 
            time +=1
            p = p.next
        
        q = head
        move = time - n -1  # 记录要移动的次数
        if move == -1:
            return head.next
        for i in range(move): # 将指针q移动到要删除的位置的前一个位置
            q = q.next
        q.next = q.next.next

        return

法二：

上述方法需要两趟遍历才能解决问题，
可以使用快慢指针一趟遍历完成操作。俩指针 slow 和fast。先将快指针fast移动n次。然后两个指针一起移动。
若快指针的下一个为空，则此时慢指针的下一个位置就是我们要删除的位置了。

还是使用刚才的例子 :链表为:head = [1,2,3,4,5], 需要删除倒数第2个节点。n = 2。

首先先让快指针往后移动 n = 2 次，然后此时慢指针指向开头，
此时让快慢指针一起往后移动。
slow = 0 fast = 2
slow = 1 fast = 3
slow = 2 fast = 4 此时fast已经指向链表末尾，所以slow的下一个元素就是需要删除的元素了。

完整代码:

# 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: ListNode, n: int) -> ListNode:
        if not head.next:
            return None 
        fast = head
        slow = head
        for i in range(n):
            fast = fast.next
        if not fast:  # 此时说明要删除的是第一个字符
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return

文章来源： https://blog.51cto.com/u_15849381/5802308

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。