前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >如何删除给定单向链表的倒数第N个元素

如何删除给定单向链表的倒数第N个元素

作者头像
一个架构师
发布2022-06-20 19:39:54
6580
发布2022-06-20 19:39:54
举报
文章被收录于专栏:从码农的全世界路过

如何删除给定单向链表的倒数第N个元素?

先分析下有哪些关键词:

1. 单向链表,那也就是我们只能单向遍历;

2. 倒数第N个元素,只能先遍历到尾部,才知道倒数第N个元素是什么,但问题又出现了,是单向链表,不能反向遍历,那该如何解决呢?

3. 删除,要想删除某一元素,是需要知道这个指定元素的前一元素才行,那我们其实要找到的倒数N+1个元素.

以如下队列为例,如果要删除倒数第2个元素,就要找到倒数第3个元素,也就是倒数第N+1个元素,那改如何做呢?

首先一定需要一个指针遍历到队列尾部的,那怎么记录这个指针已经遍历过的元素呢?可否也用一个指针记录呢.

按这个思路,首先需要一个正常的指针一直遍历到队列尾部,称之为快指针;

再需要一个比这个快指针慢N个元素的第二个指针,称之为慢指针.

两个指针按照同样的速度同时移动,当快指针到达结尾的时候,慢指针也就到达了倒数第N+1个元素的位置.

再细分下,如果要删除的目标元素正好和链表长度相同呢?那是没有前一个元素的,看来边界值需要稍做处理下,遍历的count值和N值相同时,需要直接删除首元素,不再查找前一元素

附上代码:

代码语言:javascript
复制
public class DeleteNElementFromBottom {
    static Node deleteNElementFromBottom(Node head, int n) {
        Node quickNode = head;
        Node slowNode = null;
        int count = 0;
        while (quickNode != null) {
            if (slowNode == null && count == n) {
                // 快指针已经移动过N个元素之后,慢指针才会指向链表头元素
                slowNode = head;
            } else if (slowNode != null) {
                // 慢指针后移
                slowNode = slowNode.next;
            }
            // 快指针后移
            quickNode = quickNode.next;
            // 计数,用于判断慢指针开始指向头元素时机
            // 以及,链表边界值问题
            count++;
            if (quickNode == null) {
                break;
            }
        }
        if (count == n) {
            // 删除元素正好是边界值时,返回链表第二个元素做为新链表首元素
            return head.next;
        } else {
            if (null != slowNode) {
                // 将被删除的指定元素后一元素接到前一元素上
                slowNode.next = slowNode.next.next;
            }
            return head;
        }
    }
 
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        System.out.println(print(node1));
        Node backward = deleteNElementFromBottom(node1, 2);
        System.out.println(backward);
    }
 
    static String print(Node head) {
        StringBuilder sb = new StringBuilder("Head->");
        Node p = head;
        while (p != null) {
            sb.append(p.data).append("->");
            p = p.next;
        }
        sb.append("null");
        return sb.toString();
    }
    static class Node {
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
        }
        @Override
        public String toString() {
            return "Node{data=" + data + ", next=" + next + '}';
        }
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 从码农的全世界路过 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档