Leetcode19 删除链表的倒数第N个节点 C++,Java,Python

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

博主Github：https://github.com/GDUT-Rp/LeetCode

题目：

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

示例 1:

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

解题思路：

方法一：替换内容

直观想法

设置一个tmp指针指向所给指针node的next，然后将tmp.val赋给node.val，然后将tmp.next赋给node.next，然后释放tmp空间即可。

C++

//
// Created by Lenovo on 2019/3/9.
//

#ifndef LEETCODE_C_PLUSPLUS_LEETCODE19_H
#define LEETCODE_C_PLUSPLUS_LEETCODE19_H

#include <iostream>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//struct ListNode {
//    int val;
//    ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};

class Solution_LeetCode19 {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        if (head == nullptr || n <= 0)
            return head;
        ListNode *fast = head, *slow = head;
        while(n--)
            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;
    }
};

#endif //LEETCODE_C_PLUSPLUS_LEETCODE19_H

Java

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

Python

# -*- coding: utf-8 -*-
# @File   : LeetCode19.py
# @Author : Runpeng Zhang
# @Date   : 2020/4/28
# @Desc   : Leetcode19 删除链表的倒数第N个节点


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


class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast, slow = head, head
        for _ in range(n):
            fast = fast.next
        if fast is None:
            return head.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return head

复杂度分析

时间复杂度：$O(n)$O(n)

空间复杂度：$O(1)$O(1)