结果
image.png
核心算法
//求链表的长度
public static int getLength(HeroNode head){
if (head.next == null) {
return 0;
}
HeroNode cur = head.next;
int count=0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//查找单链表的倒数第K个结点
//参数：head和k
public HeroNode getKNode(HeroNode head, int k) {
if (head.next == null) {
return null;
}
if (getLength(head) < k||k<=0) {
System.out.println(("参数小于1或者大于链表长度，无法查找"));
return null;
}
int position = getLength(head) - k + 1;//也可以去掉+1，后面的position>=0
HeroNode temp = head;
while (position >= 1) {
position--;
temp = temp.next;
}
return temp;
}
完整测试代码
package com.nan;
/**
* @author klr
* @create 2020-07-01-23:07
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.add(hero1);
singleLinkedList.add(hero2);
singleLinkedList.add(hero3);
singleLinkedList.add(hero4);
System.out.println("修改前");
singleLinkedList.list();
singleLinkedList.update(new HeroNode(1,"小宋","及时雨"));
System.out.println("修改后");
singleLinkedList.list();
System.out.println("删除结点2");
singleLinkedList.delete(2);
singleLinkedList.list();
System.out.println("查找链表的第K个结点,从1开始");
System.out.println(singleLinkedList.getKNode(singleLinkedList.getHead(), 3));
}
}
class SingleLinkedList{
//头结点，不能动，不存放具体的数据
private HeroNode head = new HeroNode(0,"","");
public HeroNode getHead() {
return head;
}
//求链表的长度
public static int getLength(HeroNode head){
if (head.next == null) {
return 0;
}
HeroNode cur = head.next;
int count=0;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//查找单链表的倒数第K个结点
//参数：head和k
public HeroNode getKNode(HeroNode head, int k) {
if (head.next == null) {
return null;
}
if (getLength(head) < k||k<=0) {
System.out.println(("参数小于1或者大于链表长度，无法查找"));
return null;
}
int position = getLength(head) - k + 1;//也可以去掉+1，后面的position>=0
HeroNode temp = head;
while (position >= 1) {
position--;
temp = temp.next;
}
return temp;
}
//找到当前链表的最后结点
//将最后这个结点的next指向新的结点
public void add(HeroNode heroNode){
//因为head结点不动，我们需要定义一个零时结点
HeroNode temp = head;
//判断英雄是否重复
boolean flag = false;
while (true) {
if (temp.next == null) {
break;
}
if (temp.next.number > heroNode.number) {
break;
} else if (temp.next.number == heroNode.number) {
flag = true;//说明该英雄存在，无法添加
break;
}
temp = temp.next;
}
if (flag) {
System.out.printf("英雄%d存在，无法添加\n",heroNode.number);
return;
}
heroNode.next=temp.next;
temp.next=heroNode;
// //遍历这个链表，找到最后
// while (true) {
// //列表为空，直接添加
// if (temp.next == null) {
// temp.next = heroNode;
// break;
// }
// //比较大小，直接插入
// if (temp.number <= heroNode.number && heroNode.number <= temp.next.number) {
// heroNode.next = temp.next;
// temp.next = heroNode;
// break;
// }
// //如果没有找到，就继续找
// temp = temp.next;
// }
}
//根据id修改结点
public void update(HeroNode newHeroNode) {
if (head.next == null) {
System.out.println("链表为空，无法修改");
return;
}
HeroNode temp = head.next;
boolean flag = false;
while (true) {
if (temp == null) {
break;//已经遍历完链表
}
if (temp.number == newHeroNode.number) {
flag=true;
break;
}
temp=temp.next;
}
if (flag) {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
}
else {
System.out.printf("未找到编号为%d的英雄\n",newHeroNode.number);
}
}
//删除结点
public void delete(int number) {
HeroNode temp = head;
if (temp.next == null) {
System.out.println("该链表为空");
return;
}
boolean flag = false;
while (true) {
if (temp.next == null) {
break;//遍历完链表
}
if (temp.next.number == number) {
flag = true;//找到结点
break;
}
temp=temp.next;
}
if (flag) {
temp.next=temp.next.next;
}
else {
System.out.printf("编号%d的英雄不存在",number);
}
}
//遍历
public void list(){
//判断链表是否为空
if (head.next == null) {
System.out.println("链表为空");
return;
}
//因为head不能动
HeroNode temp = head.next;
while (true) {
//判断是否到链表最后
if (temp == null) {
break;
}
//输出结点信息
System.out.println(temp);
//将temp后移
temp = temp.next;
}
}
}
class HeroNode {
public int number;//排名
public String name;//姓名
public String nickName;//绰号
public HeroNode next;//指针
public HeroNode(int number, String name, String nickName) {
this.number = number;
this.name = name;
this.nickName = nickName;
}
@Override
public String toString() {
return "HeroNode{" +
"number=" + number +
", name='" + name + '\'' +
", nickName='" + nickName +
'}';
}
}
网友评论