該部分包含以下內(nèi)容
-單鏈表的增刪改查
-計(jì)算鏈表長度
-逆序鏈表
-尋找（刪除）鏈表倒數(shù)第K個(gè)元素
-逆序打印鏈表（使用棧）
import java.util.Stack;
import javax.swing.text.AbstractDocument.BranchElement;
public class SingleLinkedListDemo {
public static void main(String[] args) {
// TODO Auto-generated method stub
// 先創(chuàng)建節(jié)點(diǎn)
HeroNode hero1 = new HeroNode(1, "song", "及時(shí)雨");
HeroNode hero2 = new HeroNode(2, "盧俊義", "玉麒麟");
HeroNode hero3 = new HeroNode(3, "吳用", "智多星");
HeroNode hero4 = new HeroNode(4, "林沖", "豹子頭");
// 加入節(jié)點(diǎn)
// 創(chuàng)建鏈表
Singlelinkedlist singlelinkedlist = new Singlelinkedlist();
singlelinkedlist.addByOrder(hero1);
singlelinkedlist.addByOrder(hero4);
singlelinkedlist.addByOrder(hero3);
singlelinkedlist.addByOrder(hero2);
// singlelinkedlist.addByOrder(hero3);
singlelinkedlist.showList();
HeroNode newheroNode = new HeroNode(2, "小路", "玉麒麟");
singlelinkedlist.update(newheroNode);
// singlelinkedlist.showList();
// singlelinkedlist.deletenode(4);
System.out.println();
// singlelinkedlist.showList();
// System.out.println(getLength(singlelinkedlist.getHead()));
// System.out.println(findLastIndexNode(singlelinkedlist.getHead(), 1));
// 逆序鏈表
// reverseLinkList(singlelinkedlist.getHead());
// 逆序打印
System.out.println("********************");
reverseprintList(singlelinkedlist.getHead());
System.out.println();
singlelinkedlist.showList();
}
// 獲取單鏈表的個(gè)數(shù)
public static int getLength(HeroNode head) {
if (head.next == null) {
return 0;
}
int length = 0;
HeroNode curHeroNode = head.next;
while (curHeroNode != null) {
length++;
curHeroNode = curHeroNode.next;
}
return length;
}
// 查找單鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn)
// 接收head節(jié)點(diǎn)，接收k 的index
// 先把鏈表從頭到尾遍歷一下，得到鏈表的長度
// 再遍歷size-index個(gè)節(jié)點(diǎn)
public static HeroNode findLastIndexNode(HeroNode head, int index) {
if (head.next == null) {
return null;
}
// 獲得鏈表長度
int size = getLength(head);
// 檢驗(yàn)index是否合法
if (index <= 0 || index > size) {
System.out.println("index不合法");
return null;
}
HeroNode curHeroNode = head.next;
for (int i = 1; i <= size - index; i++) {
// 走幾步到倒數(shù)第K個(gè)節(jié)點(diǎn)
curHeroNode = curHeroNode.next;
}
return curHeroNode;
}
// 單鏈表反轉(zhuǎn)
// 第一種方法：建立一個(gè)新鏈表，然后使用頭插法建立鏈表
public static void reverseLinkList(HeroNode head) {
if (head.next == null) {
return;
}
HeroNode reverseHead = new HeroNode(0, "", "");
HeroNode curHeroNode = head.next;
HeroNode nextHeroNode = null;
while (curHeroNode != null) {
// HeroNode tmpHeroNode=curHeroNode;
nextHeroNode = curHeroNode.next;
curHeroNode.next = reverseHead.next;
reverseHead.next = curHeroNode;
curHeroNode = nextHeroNode;
}
head.next = reverseHead.next;
}
public static void showreverseList(HeroNode head) {
// 判斷鏈表是否為空
if (head.next == null) {
return;
}
HeroNode tempHeroNode = head.next;
while (true) {
// 判斷是否已經(jīng)到達(dá)最后一個(gè)節(jié)點(diǎn)
if (tempHeroNode == null) {
break;
}
// 打印
System.out.println(tempHeroNode);
//
tempHeroNode = tempHeroNode.next;
}
}
// 逆序打印
public static void reverseprintList(HeroNode head) {
if (head.next == null) {
return;
}
// 創(chuàng)建一個(gè)棧艇纺，不需要自己寫
Stack<HeroNode> stack = new Stack<HeroNode>();
HeroNode curHeroNode = head.next;
while (curHeroNode != null) {
stack.push(curHeroNode);
curHeroNode = curHeroNode.next;
}
while (stack.size() > 0) {
System.out.println(stack.pop());
}
}
}
// 定義linklist
class Singlelinkedlist {
// 初始化頭節(jié)點(diǎn)
private HeroNode head = new HeroNode(0, "", "");
// 添加節(jié)點(diǎn)到單向鏈表
// 1.找到當(dāng)前鏈表的最后節(jié)點(diǎn)
// 2.將最后的next域指向最后節(jié)點(diǎn)
public void addNode(HeroNode heronode) {
HeroNode tempHeroNode = head;
while (true) {
// 獲取最后的節(jié)點(diǎn)
if (tempHeroNode.next == null) {
break;
}
tempHeroNode = tempHeroNode.next;
}
// 將最后節(jié)點(diǎn)的next
tempHeroNode.next = heronode;
}
// 按順序添加節(jié)點(diǎn)
public void addByOrder(HeroNode heronode) {
HeroNode tmpHeroNode = head;
boolean flag = false;
while (true) {
// 如果是最后一個(gè)節(jié)點(diǎn)盟劫，證明需要插入到最后急迂，直接退出
if (tmpHeroNode.next == null) {
break;
}
// 找到插入位置
if (tmpHeroNode.next.no > heronode.no) {
break;
} else if (tmpHeroNode.next.no == heronode.no) {
flag = true;
break;
}
tmpHeroNode = tmpHeroNode.next;
}
// 判斷是否能夠插入
if (flag) {
System.out.println("待插入節(jié)點(diǎn)已存在");
} else {
heronode.next = tmpHeroNode.next;
tmpHeroNode.next = heronode;
}
}
// 修改節(jié)點(diǎn)信息，編號(hào)不能變
// 根據(jù)節(jié)點(diǎn)編號(hào)修改
public void update(HeroNode newheroNode) {
// 判斷鏈表是否為空
if (head.next == null) {
System.out.println("鏈表為空");
return;
}
HeroNode tmpHeroNode = head.next;
boolean flag = false;
while (true) {
if (tmpHeroNode == null) {
break;
}
if (tmpHeroNode.no == newheroNode.no) {
flag = true;
break;
}
tmpHeroNode = tmpHeroNode.next;
}
if (flag) {
tmpHeroNode.name = newheroNode.name;
tmpHeroNode.nickname = newheroNode.nickname;
} else {
System.out.printf("編號(hào)為%d的節(jié)點(diǎn)不存在\n", newheroNode.no);
}
}
public void showList() {
// 判斷鏈表是否為空
if (head.next == null) {
return;
}
HeroNode tempHeroNode = head.next;
while (true) {
// 判斷是否已經(jīng)到達(dá)最后一個(gè)節(jié)點(diǎn)
if (tempHeroNode == null) {
break;
}
// 打印
System.out.println(tempHeroNode);
//
tempHeroNode = tempHeroNode.next;
}
}
// 單鏈表的刪除
public void deletenode(int no) {
if (head.next == null) {
System.out.println("鏈表為空");
return;
}
// 找到需要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
HeroNode tmpHeroNode = head;
boolean flag = false;
while (true) {
if (tmpHeroNode.next == null) {
break;
}
if (tmpHeroNode.next.no == no) {
flag = true;
break;
}
tmpHeroNode = tmpHeroNode.next;
}
if (flag) {
tmpHeroNode.next = tmpHeroNode.next.next;
} else {
System.out.printf("編號(hào)為%d的節(jié)點(diǎn)不存在，無法刪除\n", no);
}
}
// 獲取單鏈表的個(gè)數(shù)，不包括頭結(jié)點(diǎn)
/**
*
* @return 返回有效節(jié)點(diǎn)個(gè)數(shù)
*/
// 返回頭結(jié)點(diǎn)
public HeroNode getHead() {
return head;
}
}
//定義單個(gè)節(jié)點(diǎn)
class HeroNode {
public int no;
public String name;
public String nickname;
public HeroNode next;
public HeroNode(int no, String name, String nickname) {
super();
this.no = no;
this.name = name;
this.nickname = nickname;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
}
}
