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

LeetCode LeetCode 双指针 链表
发布时间 :
字数:1.7k 阅读 : 评论:
  1. 19.删除链表的倒数第 N 个结点
    1. 19.1 题目
    2. 19.2 题解
      1. 两趟遍历链表
      2. 双指针一趟遍历链表
    3. 19.3 代码
    4. 19.4 运行结果

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

19.1 题目

给你一个链表，删除链表的倒数第 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

进阶：你能尝试使用一趟扫描实现吗？

19.2 题解

两趟遍历链表

// 方法一：两趟遍历链表
// 遍历链表得到链表长度并计算要删除节点的索引，如果删除是头节点直接返回下一节点，再次遍历链表删除结点并返回头节点
static ListNode RemoveNthFromEnd1(ListNode head, int n)
{
    // 第一趟扫描，获取链表长度
    int length = 0;
    ListNode current1 = head;

    // 遍历链表，计算链表的长度
    while (current1 != null)
    {
        length++;
        current1 = current1.next;
    }

    // 计算待删除结点的正向索引
    int indexToDelete = length - n;

    // 如果待删除的是头结点，直接返回头结点的下一个结点
    if (indexToDelete == 0)
    {
        return head.next;
    }

    // 第二趟扫描，找到待删除结点的前一个结点
    ListNode current2 = head;

    // 遍历链表，移动 current2 到待删除结点的前一个结点
    for (int i = 0; i < indexToDelete - 1; i++)
    {
        current2 = current2.next;
    }

    // 删除结点
    current2.next = current2.next.next;

    return head;
}

双指针一趟遍历链表

// 方法二：双指针一趟遍历链表
// 一个走的快的指针或者走在前面的指针 一个走的慢的指针或者走在后面的指针
// 如果我们让快指针提前走 n步（这个n就是函数传入的要删除的倒数n个节点的n）
// 而此时我们再让慢指针和快指针一起一步一步的走，那么当快指针走到尾部时停止 
// 为了考虑移除的是头结点，所以我们需要在头结点前面加一个自定义头结点，那么在加入了一个新的头结点的前提下，这时停下来，慢指针刚好就是倒数第n个节点的前一个节点了 
static ListNode RemoveNthFromEnd2(ListNode head, int n)
{
    // 创建虚拟头结点，并将其 next 指向原链表的头结点
    ListNode fakeHead = new ListNode(Int32.MaxValue, head);

    // 初始化快慢指针，均指向虚拟头结点
    ListNode slow = fakeHead;
    ListNode fast = fakeHead;

    // 将快指针移动到正向索引为 n+1 的位置
    int fastRemain = n;
    while (fastRemain > 0)
    {
        fast = fast.next;
        fastRemain--;
    }

    // 同时移动快慢指针，直到快指针到达链表末尾
    while (fast.next != null)
    {
        fast = fast.next;
        slow = slow.next;
    }

    // 删除倒数第 n 个结点
    slow.next = slow.next.next;

    // 返回虚拟头结点的下一个结点作为新的头结点
    return fakeHead.next;
}

19.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个链表，删除链表的倒数第 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

        // 进阶：你能尝试使用一趟扫描实现吗？

        #endregion

        #region 测试

        // 示例 1
        ListNode head1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
        int n1 = 2;
        Console.Write("示例1 方法1 输出：");
        PrintList(RemoveNthFromEnd1(head1, n1));
        Console.Write("示例1 方法2 输出：");
        PrintList(RemoveNthFromEnd2(head1, n1));

        // 示例 2
        ListNode head2 = new ListNode(1);
        int n2 = 1;
        Console.Write("示例2 方法1 输出：");
        PrintList(RemoveNthFromEnd1(head2, n2));
        Console.Write("示例2 方法2 输出：");
        PrintList(RemoveNthFromEnd2(head2, n2));

        // 示例 3
        ListNode head3 = new ListNode(1, new ListNode(2));
        int n3 = 1;
        Console.Write("示例3 方法1 输出：");
        PrintList(RemoveNthFromEnd1(head3, n3));
        Console.Write("示例3 方法2 输出：");
        PrintList(RemoveNthFromEnd2(head3, n3));

        #endregion
    }

    #region 答案

    // 方法一：两趟遍历链表
    // 遍历链表得到链表长度并计算要删除节点的索引，如果删除是头节点直接返回下一节点，再次遍历链表删除结点并返回头节点
    static ListNode RemoveNthFromEnd1(ListNode head, int n)
    {
        // 第一趟扫描，获取链表长度
        int length = 0;
        ListNode current1 = head;

        // 遍历链表，计算链表的长度
        while (current1 != null)
        {
            length++;
            current1 = current1.next;
        }

        // 计算待删除结点的正向索引
        int indexToDelete = length - n;

        // 如果待删除的是头结点，直接返回头结点的下一个结点
        if (indexToDelete == 0)
        {
            return head.next;
        }

        // 第二趟扫描，找到待删除结点的前一个结点
        ListNode current2 = head;

        // 遍历链表，移动 current2 到待删除结点的前一个结点
        for (int i = 0; i < indexToDelete - 1; i++)
        {
            current2 = current2.next;
        }

        // 删除结点
        current2.next = current2.next.next;

        return head;
    }


    // 方法二：双指针一趟遍历链表
    // 一个走的快的指针或者走在前面的指针 一个走的慢的指针或者走在后面的指针
    // 如果我们让快指针提前走 n步（这个n就是函数传入的要删除的倒数n个节点的n）
    // 而此时我们再让慢指针和快指针一起一步一步的走，那么当快指针走到尾部时停止 
    // 为了考虑移除的是头结点，所以我们需要在头结点前面加一个自定义头结点，那么在加入了一个新的头结点的前提下，这时停下来，慢指针刚好就是倒数第n个节点的前一个节点了 
    static ListNode RemoveNthFromEnd2(ListNode head, int n)
    {
        // 创建虚拟头结点，并将其 next 指向原链表的头结点
        ListNode fakeHead = new ListNode(Int32.MaxValue, head);

        // 初始化快慢指针，均指向虚拟头结点
        ListNode slow = fakeHead;
        ListNode fast = fakeHead;

        // 将快指针移动到正向索引为 n+1 的位置
        int fastRemain = n;
        while (fastRemain > 0)
        {
            fast = fast.next;
            fastRemain--;
        }

        // 同时移动快慢指针，直到快指针到达链表末尾
        while (fast.next != null)
        {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除倒数第 n 个结点
        slow.next = slow.next.next;

        // 返回虚拟头结点的下一个结点作为新的头结点
        return fakeHead.next;
    }

    #endregion

    #region 辅助方法

    // 辅助方法：打印链表
    static void PrintList(ListNode head)
    {
        while (head != null)
        {
            Console.Write(head.val + " ");
            head = head.next;
        }

        Console.WriteLine();
    }

    #endregion
}

// 链表节点定义
public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

19.4 运行结果

因为同一个链表运行了两次所以结果不一致
示例1 方法1 输出：1 2 3 5 
示例1 方法2 输出：1 2 5 
示例2 方法1 输出：
示例2 方法2 输出：
示例3 方法1 输出：1 
示例3 方法2 输出：
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏