文档章节

在单链表中删除倒数第k个节点

一贱书生
 一贱书生
发布于 2016/11/16 10:24
字数 703
阅读 113
收藏 0

实现方式很多,在这里只说两种实现方式。看不懂时候,大家可以画画图,对理解为什么很有帮助。
第一种方式:
1.首先判断K值和链表是否为空,如果k<=0,或链表为空,直接返回head;
2.满足上面条件后,定义ListNode P=head,重头开始遍历链表,走k步后,退出循环(在此循环中,如果没到k,p就为null了,说明没有倒数第K个节点,k大于表长度了,直接返回head)。
3.定义ListNode q = head,与p同步向后走,直到p的next为空时候,节点为要删除节点的前一个结点。

第二种方式:
1.首先判断K值和链表是否为空,如果k<=0,或链表为空,直接返回head;
2.遍历一遍链表,每走一步,让k值减1.

3.遍历完后,如果k大于零,说明k大于链表长度,直接返回head;如果k等于0,要删除的节点就是头结点,直接返回head.next;如果k小于0的时候就第4步。
4.定义q=head,从新遍历节点,每走一步k加1,直到k=0时候,退出循环,此时q的下一个节点就是要删除的节点。

(4.解析:在这部分,为什么这样做,可能不是很容易理解,给大家举个例子,假如现在有一链表有8个节点,k=3.那么,前三步后,k=-5。大家 想一想,k等于三是要删除倒数第3个节点,我们只要从头走5步就可以到达删除节点的前一个节点了,为啥是5,因为8 = 3+5。

 

package cglib;
import java.util.Hashtable;  

 

public class StringNumber {
    // 2.在单链表中删除倒数第k个节点(方法一)
    public static ListNode removeLastKthNode(ListNode head, int k) {
        if (k <= 0 || head == null)
            return head;
        ListNode p = head;
        for (int i = 0; i < k; i++) {
            if (p.nextNode != null)
                p = p.nextNode;
            else
                return head;
        }
        ListNode q = head;
        while (p.nextNode != null) {
            p = p.nextNode;
            q = q.nextNode;
        }
        q.nextNode = q.nextNode.nextNode;
        return head;
    }

    // 2.在单链表中删除倒数第k个节点(方法二)
    public static ListNode removeLastKthNode2(ListNode
    head, int k) {
        if(k <= 0 ||head == null)return head;
        ListNode p = head;
        while(p!=null){
            p = p.nextNode;
            k--;
        }
        if(k==0)return head.nextNode;
        if(k<0){
            ListNode q = head;
            while(++k!=0){ //这里注意,先自加,再判断
                q=q.nextNode;
            }
            q.nextNode=q.nextNode.nextNode;
        }
        return head;
    }
    // 创建链表
    public static ListNode creatListNode(int data[]) {
        ListNode head = new ListNode (data[0]);
        ListNode temp = head;
        for (int i = 1; i < data.length; i++) {
            ListNode headNext = new ListNode(data[i]);
            temp.nextNode = headNext;
            temp = temp.nextNode;
        }
        return head;
    }

    // 测试
    public static void main(String[] args) {
        int[] data1 = { 1, 2, 4, 5, 6, 7 };
        ListNode head1 = creatListNode(data1);
        //在单链表中删除倒数第k个节点
        ListNode head = removeLastKthNode2(head1, 1);
        while (head != null) {
            System.out.println(head.values);
            head = head.nextNode;
        }
    }
}

// 链表节点类
class ListNode {
    public int values;
    public ListNode nextNode;

    public ListNode(int data) {
        this.values = data;
    }
    
}
      


输出:

1
2
4
5
6

 

© 著作权归作者所有

一贱书生
粉丝 20
博文 724
码字总数 600123
作品 0
私信 提问
数据结构之链表与数组(2):单向链表上的简单操作问题

原文出处:写代码的李纳 本文主要介绍一些解决单向链表上部分操作问题的思路和代码实现。 主要的问题包括以下几点: 向单向链表中插入一个节点 删除单向链表中的一个节点 查找单向链表中的一...

写代码的李纳
2015/11/11
0
0
经典单链表练习题(2)

问题: 删除链表的倒数第K个结点 判断单链表是否带环?若带环,求环的长度?求环的入口点?并计算每个算法的时间复杂度&空间复杂度。 判断两个链表是否相交,若相交,求交点。(假设链表不带...

triorwy
2018/01/24
0
0
链表的基本操作

datacube
2016/07/07
18
0
Java实现链表面试题

本文包含链表的以下内容:   1、单链表的创建和遍历   2、求单链表中节点的个数   3、查找单链表中的倒数第k个结点(剑指offer,题15)   4、查找单链表中的中间结点   5、合并两个...

火力全開
2016/10/09
51
0
面试精选之链表问题集锦

链表问题是面试过程中经常被问到的一部分,很考查编程功底。最近刷了 LeetCode 上链表部分的面试题,我总结了一些有代表性的链表问题。 本文使用的是 Java 语言,下面是所用到的链表节点的定...

JohnnyShieh
2017/11/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java快递电子面单打印接口对接demo

之前的后天管理系统的电子面单打印使用的是灵通打单。 使用相对比较麻烦,需要到处Excel之后再导入,麻烦。 快递鸟有电子面单api,后台系统直接对接很是方便,不过也遇到了好些问题。 不难是...

程序的小猿
26分钟前
3
0
fasjtjson文档

https://github.com/alibaba/fastjson/wiki/JSONField

jirak
26分钟前
3
0
Mybatis中插入多条记录

Oracle数据库 实现方法 <insert id="saveWithdrawLog"> INSERT ALL INTO OSM_TRADE_DETAIL(SID,MBR_ID,USR_ID,TRADE_MONEY,TRADE_TYPE,TRADE_TIME,TRADE_WAY,PAY_ID) VALUES(#{si......

豫华商
27分钟前
3
0
Flink on YARN(下):常见问题与排查思路

作者:杨弢(搏远) Flink 支持 Standalone 独立部署和 YARN、Kubernetes、Mesos 等集群部署模式,其中 YARN 集群部署模式在国内的应用越来越广泛。Flink 社区将推出 Flink on YARN 应用解读...

开源中国小二
28分钟前
3
0
技术沙龙|京东云端到端多媒体关键技术揭秘

编者按:从带来更高编码效率、更好的用户体验的京享高清,到直播架构与网络演进优化,从而为用户带来更流畅的观看体验,以及运维系统的异常自动修复和高弹性的多媒体存储架构,一层一层展示出...

京东云技术新知
29分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部