【韩顺平

【韩顺平

一、单链表

1、单链表概述

1. 链表是以节点的方式来存储,是链式存储
2. 每个节点包含data域， next 域：指向下一个节点.
3. 链表的各个节点不一定是连续存储
4. 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确

2、面试题

1）有效节点个数

/*** 有效节点个数（遍历+计数）*/
public int usedNode() {int ans = 0;heroNode temp = head;while ( != null) {ans++;temp = ;}return ans;
}

2）倒数第K个节点数据

/*** 反向输出第k个节点*/
public void oppoShow(int k) {int all = usedNode();heroNode temp = ;if (all < k) {System.out.printf("没有第%d个节点n", k);return;}int i = 1;while (temp != null) {if (i == (all - k + 1)) {System.out.String());break;}temp = ;i++;}
}

3）反向遍历——迭代

/*** 反向遍历*/
public void oppoShow() {if ( == null) {System.out.println("链表为空");return;}int all = usedNode();for (int i = all; i >= 0; i--) {int j = 1;heroNode temp = ;while (temp != null) {if (j == i) {System.out.String());break;}j++;temp = ;}}
}

4）反向遍历——栈

class nodeStact {int maxSize;heroNode[] hn;int top;/*** 栈的构造器* * @param maxSize 栈的大小*/nodeStact(int maxSize) {this.maxSize = maxSize;hn = new heroNode[maxSize];top = -1;}/*** 判空*/public boolean isEmpty() {return top == -1;}/*** 判满*/public boolean isFull() {return top == maxSize - 1;}/*** 弹出*/public heroNode pop() {if (isEmpty()) {System.out.println("栈空");return null;}return hn[top--];}/*** 压栈*/public void push(heroNode _hn) {if (isFull()) {System.out.println("栈满");} else {hn[++top] = _hn;}}
}

/*** 反向遍历——通过栈实现*/
public void showByStack() { == null) {System.out.println("链表为空");return;}nodeStact ns = new nodeStact(usedNode());heroNode temp = ;while(temp != null) {ns.push(temp);temp = ;}while(!ns.isEmpty()) {System.out.println(ns.pop().toString());}
}

5）合并单链表

/*** 与demo合并*/
public void mesh() {singleLinkedList demo = new singleLinkedList();demo.add(new heroNode(-1, "小明", "王哥"));demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));heroNode temp = ;while(temp != null) {addByNo(new No(), Name(), NickName()));temp = ;}}

3、代码实现

hao.linkedlist;import java.util.Scanner;public class singleLinkedListDemo {public static void main(String[] args) {singleLinkedList sll = new singleLinkedList();boolean loop = true;while (loop) {System.out.println("--------");System.out.println("1.在尾部添加");System.out.println("2.按编号添加");System.out.println("3.遍历单链表");System.out.println("4.修改节点");System.out.println("5.删除节点");System.out.println("6.有效节点个数");System.out.println("7.反向输出");System.out.println("8.反向遍历");System.out.println("0.退出");System.out.println("--------");Scanner sc = new Scanner(System.in);int key = sc.nextInt();if (key == 1) {System.out.println("请输入英雄编号：");int no = sc.nextInt();System.out.println("请输入英雄姓名：");Scanner sc1 = new Scanner(System.in);String name = Line();System.out.println("请输入英雄昵称：");Scanner sc2 = new Scanner(System.in);String nickName = Line();sll.add(new heroNode(no, name, nickName));System.out.println("添加成功！");} else if (key == 2) {System.out.println("请输入英雄编号：");int no = sc.nextInt();System.out.println("请输入英雄姓名：");Scanner sc1 = new Scanner(System.in);String name = Line();System.out.println("请输入英雄昵称：");Scanner sc2 = new Scanner(System.in);String nickName = Line();sll.addByNo(new heroNode(no, name, nickName));System.out.println("添加成功！");} else if (key == 3) {try {sll.show();} catch (Exception e) {System.out.Message());}} else if (key == 4) {System.out.println("请输入英雄编号：");int no = sc.nextInt();System.out.println("请输入英雄新的姓名：");Scanner sc1 = new Scanner(System.in);String name = Line();System.out.println("请输入英雄新的昵称：");Scanner sc2 = new Scanner(System.in);String nickName = Line();sll.change(no, name, nickName);} else if (key == 5) {System.out.println("请输入英雄编号：");int no = sc.nextInt();sll.delete(no);} else if (key == 6) {System.out.println("有效节点个数：" + sll.usedNode());} else if (key == 7) {int k = sc.nextInt();sll.oppoShow(k);} else if (key == 8) {System.out.println("通过反向遍历实现：");sll.oppoShow();System.out.println("通过栈实现：");sll.showByStack();} else if (key == 9) {System.out.println("与demo链表合并");sh();} else if (key == 0) {loop = false;} else {System.out.println("输入有误！");}}}
}/*** 管理英雄*/
class singleLinkedList {/*** 定义一个头结点*/private heroNode head = new heroNode(0, "", "");/*** 添加节点的方法(尾插法) 将最后的next域指向新的node*/public void add(heroNode hn) {// 需要一个辅助变量heroNode temp = head;// 遍历单链表while ( != null) {temp = ;}// 退出循环时，temp指向最后 = hn;}/*** 按照编号大小添加* * @param hn*/public void addByNo(heroNode hn) {/*** 空链表：直接放后面*/if ( == null) { = hn;return;}heroNode temp = ;/*** 如果只有一个节点，且大于hn*/if (hn.getNo() < No()) { =  = temp;return;}while (true) {/*** 如果no相等：报错*/if (hn.getNo() == No()) {throw new RuntimeException("编号重复！");}if ( != null) {if (hn.getNo() == No()) {throw new RuntimeException("编号重复！");}}/*** 找到：大于前一个节点且（小于后一个节点或者后一个节点为null）的节点*/if (hn.getNo() > No() && ( == null || hn.getNo() < No())) {hn.next = ; = hn;break;}if ( != null) {temp = ;} else {break;}}}/*** 遍历*/public void show() {// 判空if ( == null) {throw new RuntimeException("链表为空");}// 遍历heroNode temp = ;while (temp != null) {System.out.String());temp = ;}}/*** 修改节点*/public void change(int no, String name, String nickName) {// 判空if ( == null) {System.out.println("链表为空");return;}// 遍历：找no节点heroNode temp = ;while (temp != null) {if (No() == no) {temp.setName(name);temp.setNickName(nickName);System.out.println("修改成功！");return;}temp = ;}System.out.printf("未找到编号为%d的节点n", no);return;}/*** 删除节点*/public void delete(int no) {// 判空if ( == null) {System.out.println("链表为空");return;}// 遍历找节点heroNode temp = head;while ( != null) {if (No() == no) { = ;System.out.println("删除成功");return;}temp = ;}System.out.printf("未找到编号为%d的节点n", no);return;}/*** 有效节点个数（遍历+计数）*/public int usedNode() {int ans = 0;heroNode temp = head;while ( != null) {ans++;temp = ;}return ans;}/*** 反向输出第k个节点*/public void oppoShow(int k) {int all = usedNode();heroNode temp = ;if (all < k) {System.out.printf("没有第%d个节点n", k);return;}int i = 1;while (temp != null) {if (i == (all - k + 1)) {System.out.String());break;}temp = ;i++;}return;}/*** 反向遍历——翻转单链表*/public void oppoShow() {if ( == null) {System.out.println("链表为空");return;}int all = usedNode();for (int i = all; i >= 0; i--) {int j = 1;heroNode temp = ;while (temp != null) {if (j == i) {System.out.String());break;}j++;temp = ;}}}/*** 反向遍历——通过栈实现*/public void showByStack() {if ( == null) {System.out.println("链表为空");return;}nodeStact ns = new nodeStact(usedNode());heroNode temp = ;while (temp != null) {ns.push(temp);temp = ;}while (!ns.isEmpty()) {System.out.println(ns.pop().toString());}}/*** 与demo合并*/public void mesh() {singleLinkedList demo = new singleLinkedList();demo.add(new heroNode(-1, "小明", "王哥"));demo.add(new heroNode(0, "芭芭拉", "芭芭拉冲鸭"));heroNode temp = ;while(temp != null) {addByNo(new No(), Name(), NickName()));temp = ;}}
}/*** 定义heroNode节点*/
class heroNode {private int no;private String name;private String nickName;public heroNode next;/*** 构造器* * @param no       编号* @param name     姓名* @param nickName 昵称*/heroNode(int no, String name, String nickName) {this.name =  = no;this.nickName = nickName;}/*** 重写toString*/@Overridepublic String toString() {return "[no=" + no + ", name=" + name + ", nickName=" + nickName + ", next=" + next + "]";}public int getNo() {return no;}public void setNo(int no) { = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public String getNickName() {return nickName;}public void setNickName(String nickName) {this.nickName = nickName;}}class nodeStact {int maxSize;heroNode[] hn;int top;/*** 栈的构造器* * @param maxSize 栈的大小*/nodeStact(int maxSize) {this.maxSize = maxSize;hn = new heroNode[maxSize];top = -1;}/*** 判空*/public boolean isEmpty() {return top == -1;}/*** 判满*/public boolean isFull() {return top == maxSize - 1;}/*** 弹出*/public heroNode pop() {if (isEmpty()) {System.out.println("栈空");return null;}return hn[top--];}/*** 压栈*/public void push(heroNode _hn) {if (isFull()) {System.out.println("栈满");} else {hn[++top] = _hn;}}
}

二、双向链表

1、双向链表概述

2、代码实现

hao.linkedlist;import java.util.Scanner;public class doubleLinkedListDemo {public static void main(String[] args) {doubleLinkedList dll = new doubleLinkedList();boolean loop = true;while (loop) {System.out.println("--------");System.out.println("1.在尾部添加");System.out.println("2.按编号添加");System.out.println("3.遍历双向链表");System.out.println("4.修改节点");System.out.println("5.删除节点");System.out.println("6.有效节点个数");System.out.println("0.退出");System.out.println("--------");Scanner sc = new Scanner(System.in);int key = sc.nextInt();if (key == 1) {System.out.println("请输入学生编号：");int no = sc.nextInt();System.out.println("请输入学生姓名：");Scanner sc1 = new Scanner(System.in);String name = Line();dll.add(new stuNode(no, name));System.out.println("添加成功！");} else if (key == 2) {System.out.println("请输入学生编号：");int no = sc.nextInt();System.out.println("请输入学生姓名：");Scanner sc1 = new Scanner(System.in);String name = Line();dll.addByNo(new stuNode(no, name));System.out.println("添加成功！");} else if (key == 3) {dll.show();} else if (key == 4) {System.out.println("请输入学生编号：");int no = sc.nextInt();System.out.println("请输入学生新的姓名：");Scanner sc1 = new Scanner(System.in);String name = Line();dll.change(new stuNode(no, name));} else if (key == 5) {System.out.println("请输入学生编号：");int no = sc.nextInt();dll.delete(no);} else if (key == 6) {System.out.println("有效节点个数：" + dll.usedNode());} else if (key == 0) {loop = false;} else {System.out.println("输入有误！");}}}}/*** 双向链表*/
class doubleLinkedList {private stuNode head = new stuNode(0, "wmh");/*** 有效节点数*/public int usedNode() {int ans = 0;stuNode temp = ;while (temp != null) {ans++;temp = ;}return ans;}/*** 插入*/public void add(stuNode sn) {if ( == null) { = sn;sn.pre = head;return;}stuNode temp = ;while (true) {if ( == null) {break;}temp = ;} = sn;sn.pre = temp;}/*** 遍历*/public void show() {if ( == null) {System.out.println("单链表为空");return;}stuNode temp = ;while (temp != null) {System.out.println(temp);temp = ;}}/*** 修改*/public void change(stuNode sn) {if ( == null) {System.out.println("单链表为空");return;}stuNode temp = ;while (temp != null) {if (No() == sn.getNo()) {temp.Name());temp.No());return;}temp = ;}System.out.printf("未找到no=%d的节点n", sn.getNo());}/*** 自我删除*/public void delete(int no) {if ( == null) {System.out.println("链表为空");return;}stuNode temp = ;while (temp != null) {if (No() == no) {/** 找到了*/ = ;if ( != null) {pre = temp.pre;}return;}temp = ;}System.out.printf("未找到no=%d的节点n", no);}/*** 按照编号添加*/public void addByNo(stuNode sn) {/** 判空*/if ( == null) { = sn;sn.pre = head;return;}/** 判同*/stuNode temp = ;while (temp != null) {if (No() == sn.getNo()) {System.out.println("编号相同");return;}temp = ;}/** 找位置添加——第一个位置*/if (sn.getNo() < No()) {sn.next = ; = sn;sn.pre = pre = sn;return;}/** 找位置添加——不是第一个位置*/temp = ;while (temp != null) {if ( == null) { = sn;sn.pre = temp;return;}if (No() < sn.getNo() && No() > sn.getNo()) {sn.next = ; = sn;sn.pre = pre = sn;return;}temp = ;}}
}/*** 定义stuNode节点*/
class stuNode {private int no;private String name;public stuNode next;public stuNode pre;/*** 构造器* * @param no   编号* @param name 姓名*/stuNode(int no, String name) {this.name =  = no;}public int getNo() {return no;}/*** 重写toString*/@Overridepublic String toString() {return "[no=" + no + ", name=" + name + "]";// 使用双向链表，不能打印next和pre}public void setNo(int no) { = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}
}

三、单项循环链表与Josepfu问题

1、约瑟夫环概述

设编号为1,2,⋯n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

2、解决思想

用一个不带头结点的循环链表来处理 Josephu 问题：先构成一个有口个结点的单循环链表，然后由k结点起从1 开始计数，计到 m 时，对应结点从链表中州除，然后再从被删除结点的下一个结点又从1 开始计数，到最后一个结点从链表中删除算法结束。

3、代码实现

hao.linkedlist;import java.util.Scanner;public class JosepfuDemo {public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.print("总人数:");int n = sc.nextInt();System.out.print("报号数:");int k = sc.nextInt();Josepfu(n, k);}/*** Josepfu问题* * @param n 人数* @param k 报号数*/public static void Josepfu(int n, int k) {circleSingleLinkedList csll = new circleSingleLinkedList();for(int i = 1; i <= n; i++) {csll.add(new Node(i));}Node temp = csll.head;int j = 1;while(csll.usedNode() != 1) {if(j == k) {csll.Num());j = 1;temp = ;continue;}j++;temp = ;}csll.show();}
}class circleSingleLinkedList {public Node head = null;/*** 添加节点*/public void add(Node n) {/** 空链表，直接放后面*/if (head == null) {head =  = head;return;}/** 非空，遍历加在后面*/Node temp = head;while ( != head) {temp = ;} =  = head;}/*** 遍历*/public void show() {Node temp = head;boolean loop = true;while (loop) {System.out.println(temp);temp = ;if (temp == head) {loop = false;}}}/*** 有效元素*/public int usedNode() {if (head == null) {return 0;}if ( == head) {return 1;}Node temp = head;int ans = 1;while ( != head) {temp = ;ans++;}return ans;}/*** 删除节点*/public void delete(int num) {/** 判空*/if (head == null) {System.out.println("链表为空");return;}/** 删除head节点*/if (Num() == num) {if ( == head) {/** 只有一个head*/head = null;} else {/** 还有其他节点*/// 1.改最后的nextNode temp = head;while (true) {if ( == head) { = ;break;}temp = ;}// 2.改headhead = ;}return;}/** 删除其他的节点*/Node temp = ;while (true) {if (Num() == num) { = ;return;}temp = ;}}
}class Node {private int num;public Node next;Node(int num, Node next) {this.num =  = next;}Node(int num) {this.num =  = null;}@Overridepublic String toString() {return "Node[num=" + num + "]";}public int getNum() {return num;}public void setNum(int num) {this.num = num;}}

更多文章欢迎访问RexHao博客：链表 | RexHao Blog