Loading...
百度&必应权4, 日IP8000. 查看详情
自助收录

19. 删除链表的倒数第 N 个结点(解法二:双指针算法)

算法刷题2年前 (2023)更新 江南白衣
562 0 0
19. 删除链表的倒数第 N 个结点(解法二:双指针算法)

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

19. 删除链表的倒数第 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]
分析:
这道题是双指针算法的经典应用,如果要删除倒数第n个节点,可以先让fast指针移动n步,然后让fast和slow同时向后移动,直到fast指针指向链表最后一个元素,删掉slow所指向的节点就可以了。
思路是这样的,但要注意一些细节。
分为如下几步:
第一步:使用虚拟头结点,这样不用考虑头结点的特殊处理情况。
第二步:定义fast指针和slow指针,初始值为虚拟头结点
第三步:fast首先走n+1步 ,为什么是n+1呢,因为只有这样同时移动的时候slow才能指向删除节点的上一个节点(方便做删除操作):
第四步:fast和slow同时移动,直到fast指向末尾
第五步:删除slow指向的下一个节点
复杂度分析
时间复杂度:O(L)O(L),其中 LL 是链表的长度。
空间复杂度:O(1)O(1)。

package com.codernav.demo.leetcode.linkedlist.removeElements;

import com.codernav.demo.common.ListNode;

/**
 * @title 19. 删除链表的倒数第 N 个结点(双指针)
 * @Description 给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
 * @Author 开发者导航
 * @website https://www.codernav.com
 * @date 2023/3/4
 */
public class Q_19_1 {
    public static void main(String[] args) {
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        // 双指针
        ListNode head = removeNthFromEnd(node1, 2);
        System.out.println(head);
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        //只要快慢指针相差 n个结点即可
        for (int i = 0; i < n; i++) {
            fastIndex = fastIndex.next;
        }

        while (fastIndex.next != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        //此时 slowIndex 的位置就是待删除元素的前一个位置。
        //具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
        slowIndex.next = slowIndex.next.next;
        return dummyNode.next;
    }
}

 

 

© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...