当前位置：
  1. 首页
  2. 数据结构与算法
  3. 算法系统课
  4. 正文

LeetCode19. 删除链表的倒数第 N 个结点🌟🌟🌟🌟🌟中等

算法系统课 免费

课后作业

问题描述

原文链接：19. 删除链表的倒数第 N 个结点

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

示例 1：

img

输入：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

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null){
            return head;
        }
        int k = 0;
        ListNode temp = head;
        while(temp != null){
            k++;
            temp = temp.next;
        }

        // index
        int index = k - n + 1;
        if(index == 1){
            return head.next;
        }
        ListNode pre = head;
        while(index > 2){
            index --;
            pre = pre.next;
        }

        pre.next = pre.next.next;
        return head;
    }

}

Python

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

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        if not head:
            return head

        k = 0
        temp = head
        while temp:
            k += 1
            temp = temp.next

        # index
        index = k - n + 1
        if index == 1:
            return head.next
        pre = head
        while index > 2:
            index -= 1
            pre = pre.next

        pre.next = pre.next.next
        return head

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head){
            return head;
        }
        int k = 0;
        ListNode* temp = head;
        while(temp){
            k++;
            temp = temp->next;
        }

        // index
        int index = k - n + 1;
        if(index == 1){
            return head->next;
        }
        ListNode* pre = head;
        while(index > 2){
            index --;
            pre = pre->next;
        }

        pre->next = pre->next->next;
        return head;
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    if head == nil {
        return head
    }
    k := 0
    temp := head
    for temp != nil {
        k++
        temp = temp.Next
    }

    // index
    index := k - n + 1
    if index == 1 {
        return head.Next
    }
    pre := head
    for index > 2 {
        index--
        pre = pre.Next
    }

    pre.Next = pre.Next.Next
    return head
}

发表回复

后才能评论

评论(9)

  • 我来吃饭啦 永久会员 2024年6月17日 下午11:35 
    # 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]:
        dummy = ListNode(0, head)
        slow, fast = dummy, dummy
        for _ in range(n):
            fast = fast.next

        while fast.next:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next #不可以写 slow.next = fast (删除头节点会出问题）
        return dummy.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: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        cur, length = head, 0
        while cur:
            length += 1
            cur = cur.next
        cur = dummy
        for _ in range(length - n):
            cur = cur.next
        cur.next = cur.next.next
        return dummy.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: Optional[ListNode], n: int) -> Optional[ListNode]:
        if not head:
            self.count = 0
            return head
        head.next = self.removeNthFromEnd(head.next, n)
        self.count += 1
        return head.next if self.count == n else head
  • Mr.肖 永久会员 2024年3月25日 下午9:20 
    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {



        ListNode dummy = new ListNode();
        dummy.next = head;

        ListNode slow = dummy;

        //待删除元素的位置
        ListNode target = head;
        ListNode fast = dummy;

        for(int i = 0; i < n; i++){
            fast = fast.next;
        }

        //fast走到链表最后一个元素时，slow是待删除结点的前一个位置
        while(fast.next != null){
            slow =slow.next;
            target = target.next;
            fast = fast.next;
        }

        slow.next = target.next;
        target.next = null;




        //这里不能直接返回head，因为head可能是要删除的元素
        //应该返回dummy.next
        return dummy.next;
    }
}
  • Yuki 永久会员 2024年1月28日 上午10:22

    和上一题差不多，加个虚拟头结点统一操作，不计入今天的刷题

    ”’
    class Solution {
    public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode*dummyHead=new ListNode(0);
    dummyHead->next=head;

        ListNode*slow=dummyHead;
    ListNode*fast=dummyHead;

    while(n--){
        fast=fast->next;
    }
    while(fast->next!=nullptr){
        slow=slow->next;
        fast=fast->next;
    }
    slow->next=slow->next->next;

    return dummyHead->next;
}

    };
    ”’

  • uu 永久会员 2023年9月19日 下午5:04

    /**
    * Definition for singly-linked list.
    * public class ListNode {
    * int val;
    * ListNode next;
    * ListNode() {}
    * ListNode(int val) { this.val = val; }
    * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    * }
    */

    // 【思路】单指针
    // class Solution {
    // public ListNode removeNthFromEnd(ListNode head, int n) {
    // ListNode cnt = head;
    // int count = 2;
    // if(cnt.next null) return null;
    // while(cnt.next.next != null) {
    // count++;
    // cnt = cnt.next;
    // }
    // if(n     1) {
    // cnt.next = null;
    // return head;
    // }
    // int i = count – n;
    // if(i 0) {
    // return head = head.next;
    // }
    // cnt = head;
    // while(i > 1) {
    // cnt = cnt.next;
    // i–;
    // }
    // cnt.next = cnt.next.next;
    // return head;
    // }
    // }

    // 【思路】双指针
    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode pre = head;
    ListNode sub = head;
    if(sub.next null) return null;
    while(sub.next != null) {
    sub = sub.next;
    n–;
    if(n > -1) {
    continue;
    }
    pre = pre.next;
    }
    if(pre     head && n 1) {
    return head.next;
    }
    pre.next = pre.next.next;
    return head;
    }
    }

  • 泡芙 永久会员 2023年9月1日 下午5:49

    方法一：快慢指针(不使用虚拟头结点)

    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;

        // 链表为空
        if (head == null) {
            return head;
        }

        // fast 先移动 n 步
        for (int i = 0; i < n; i ++) {
            fast = fast.next;
        }

        // 如果删除的是头节点，即只有一个元素
        if (fast == null) {
            return head.next;
        }

        // 当slow走到n-1个节点时，就是待删除节点的前驱节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

    方法二：统计节点个数再定位删除

    lass Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 链表为空
        if (head == null) {
            return head;
        }

        // 统计节点个数
        int k = 0;
        ListNode temp = head;
        while (temp != null) {
            k ++;
            temp = temp.next;
        }

        // 待删除节点
        int index = k - n + 1;

        // 删除头节点
        if (index == 1) {
            return head.next;
        }

        ListNode pre = head;
        while (index > 2) {
            index --;
            pre = pre.next;
        }
        pre.next = pre.next.next;
        return head;
    }
}
  • Thaddeus 永久会员 2023年8月29日 下午3:25
    快慢指针，不使用虚拟头结点
    class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       if(head == nullptr) return head;

       ListNode* fast = head;
       ListNode* slow = head;
       for(int i = 0; i < n; i++) {
           fast = fast->next;
       }

       if(fast == nullptr) return head->next;
       while(fast->next != nullptr) {
           fast = fast->next;
           slow = slow->next;
       }

       slow->next = slow->next->next;
       return head;
    }
};
  • 阿尚 普通 2023年8月17日 上午10:56 
    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
       //删除节点使用虚拟节点比较方便，还能防止出错
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode fast = head;

        while(n-- > 0){
            fast = fast.next;
        }

        while(fast != null){
            pre = pre.next;
            fast = fast.next;
        }

        pre.next = pre.next.next;

        return dummy.next;
    }
}
  • 3_🔥 永久会员 2023年7月9日 下午10:26 
    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null){
            return head;
        }
        int k = 0;
        ListNode temp = head;
        while(temp != null){
            k++;
            temp = temp.next;
        }
        ListNode cur = head;
        int index = k - n + 1;
        if(index == 1) return head.next;
        for (int i = 1; i < index - 1; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return head;
    }
}

    index 1记得考虑

  • 帅气的冬瓜 普通 2023年6月27日 上午11:24

    打卡

如果您已经成功付款但是网站没有弹出成功提示，请联系站长提供付款信息为您处理