栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

双指针-删除链表倒数第k个节点

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

双指针-删除链表倒数第k个节点

实现语言:java

问题描述:

如果给定一个链表,删除该链表的倒数第k个节点;

假设链表中节点总数为n,那么1<=k<=n。要求只能遍历链表一次。

方法:双指针法
* 任务:删除倒数第k个节点
* 要求:只能遍历一遍链表
* 步骤:①设置两个指针,同时指向头结点(注意:只能指向head)
* ②第一个指针移动k步,第二个指针不动
* ③从第一个指针的k+1步开始,指针2与指针1同步移动
* ④当指针1指向最后一个节点时,指针2的下一个节点就是需要删除的第k个节点
* 注意:题目并不知道到链表的长度,且要求只能遍历一次,
* 另一种方法:求倒数第k个就是求正数第n-k+1个不可行,n不知道,得到n就需要遍历一次,不符合要求
* 注意事项:两个指针必须指向head,否则删除不了第一个节点,也就是倒数第n个

代码:

public class Double_pointer_List_Demo {
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        list L1 = new list();
        //把五个节点添加到链表
        L1.add(n1);
        L1.add(n2);
        L1.add(n3);
        L1.add(n4);
        L1.add(n5);
        //删除第k个节点观察结果
        L1.delete_inverse(5);
        L1.show_list();

    }
}

//链表类
class list{

    //属性:头结点
    Node head = new Node(0);

    //空构造函数
    public list(){

    }

    //方法:添加节点
    public void add(Node node){//方便起见,直接在链表的最后添加
        if(head .next == null){//链表为空
            head.next = node;
            return;
        }

        //链表不为空
        Node temp = head.next;
        while(true){
            if (temp.next == null){
                temp.next = node;
                return;
            }
            temp = temp.next;
        }
    }

    //遍历节点
    public void show_list(){
        Node temp = head.next;
        while (true){
            if (temp != null){
                System.out.println(temp.toString());
                temp = temp.next;
            }else {
                break;
            }
        }
    }


    //方法:删除倒数第k个节点
    
    public void delete_inverse(int k){
        //判断链表是否为空
        if (head == null){
            System.out.println("指针为空!");
            return;
        }

        //判断k值是否合法:题目中已经规定了k的范围,故省略这个步骤

        //定义两个指针,全都指向头结点或第一个节点
        Node n1 = head;
        Node n2 = head;
        int count = 0;
        while (n1.next != null){
            if (count >= k){
                n2 = n2.next;
            }
            n1 = n1.next;
            count = count + 1;//移动的步数

        }
        //循环结数后,n2的下一个节点就是需要删除的节点
        n2.next = n2.next.next;

    }
}

//结点类
class Node{
    int id;
    Node next;

    public Node(int id){
        this.id = id;
    }

    @Override
    public String toString() {
        return "Node{" +
                "id=" + id +
                '}';
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970623.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号