【韩顺平

admin管理员组

文章数量:1794759

【韩顺平

一、单链表

1、单链表概述

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

2、面试题

1）有效节点个数

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

2）倒数第K个节点数据

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

3）反向遍历——迭代

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

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() {if(head.next == null) {System.out.println("链表为空");return;}nodeStact ns = new nodeStact(usedNode());heroNode temp = head.next;while(temp != null) {ns.push(temp);temp = temp.next;}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 = demo.head.next;while(temp != null) {addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));temp = temp.next;}}

3、代码实现

package work.rexhao.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 = sc1.nextLine();System.out.println("请输入英雄昵称：");Scanner sc2 = new Scanner(System.in);String nickName = sc2.nextLine();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 = sc1.nextLine();System.out.println("请输入英雄昵称：");Scanner sc2 = new Scanner(System.in);String nickName = sc2.nextLine();sll.addByNo(new heroNode(no, name, nickName));System.out.println("添加成功！");} else if (key == 3) {try {sll.show();} catch (Exception e) {System.out.println(e.getMessage());}} else if (key == 4) {System.out.println("请输入英雄编号：");int no = sc.nextInt();System.out.println("请输入英雄新的姓名：");Scanner sc1 = new Scanner(System.in);String name = sc1.nextLine();System.out.println("请输入英雄新的昵称：");Scanner sc2 = new Scanner(System.in);String nickName = sc2.nextLine();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链表合并");sll.mesh();} 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 (temp.next != null) {temp = temp.next;}// 退出循环时，temp指向最后temp.next = hn;}/*** 按照编号大小添加* * @param hn*/public void addByNo(heroNode hn) {/*** 空链表：直接放后面*/if (head.next == null) {head.next = hn;return;}heroNode temp = head.next;/*** 如果只有一个节点，且大于hn*/if (hn.getNo() < temp.getNo()) {head.next = hn;hn.next = temp;return;}while (true) {/*** 如果no相等：报错*/if (hn.getNo() == temp.getNo()) {throw new RuntimeException("编号重复！");}if (temp.next != null) {if (hn.getNo() == temp.next.getNo()) {throw new RuntimeException("编号重复！");}}/*** 找到：大于前一个节点且（小于后一个节点或者后一个节点为null）的节点*/if (hn.getNo() > temp.getNo() && (temp.next == null || hn.getNo() < temp.next.getNo())) {hn.next = temp.next;temp.next = hn;break;}if (temp.next != null) {temp = temp.next;} else {break;}}}/*** 遍历*/public void show() {// 判空if (head.next == null) {throw new RuntimeException("链表为空");}// 遍历heroNode temp = head.next;while (temp != null) {System.out.println(temp.toString());temp = temp.next;}}/*** 修改节点*/public void change(int no, String name, String nickName) {// 判空if (head.next == null) {System.out.println("链表为空");return;}// 遍历：找no节点heroNode temp = head.next;while (temp != null) {if (temp.getNo() == no) {temp.setName(name);temp.setNickName(nickName);System.out.println("修改成功！");return;}temp = temp.next;}System.out.printf("未找到编号为%d的节点\n", no);return;}/*** 删除节点*/public void delete(int no) {// 判空if (head.next == null) {System.out.println("链表为空");return;}// 遍历找节点heroNode temp = head;while (temp.next != null) {if (temp.next.getNo() == no) {temp.next = temp.next.next;System.out.println("删除成功");return;}temp = temp.next;}System.out.printf("未找到编号为%d的节点\n", no);return;}/*** 有效节点个数（遍历+计数）*/public int usedNode() {int ans = 0;heroNode temp = head;while (temp.next != null) {ans++;temp = temp.next;}return ans;}/*** 反向输出第k个节点*/public void oppoShow(int k) {int all = usedNode();heroNode temp = head.next;if (all < k) {System.out.printf("没有第%d个节点\n", k);return;}int i = 1;while (temp != null) {if (i == (all - k + 1)) {System.out.println(temp.toString());break;}temp = temp.next;i++;}return;}/*** 反向遍历——翻转单链表*/public void oppoShow() {if (head.next == null) {System.out.println("链表为空");return;}int all = usedNode();for (int i = all; i >= 0; i--) {int j = 1;heroNode temp = head.next;while (temp != null) {if (j == i) {System.out.println(temp.toString());break;}j++;temp = temp.next;}}}/*** 反向遍历——通过栈实现*/public void showByStack() {if (head.next == null) {System.out.println("链表为空");return;}nodeStact ns = new nodeStact(usedNode());heroNode temp = head.next;while (temp != null) {ns.push(temp);temp = temp.next;}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 = demo.head.next;while(temp != null) {addByNo(new heroNode(temp.getNo(), temp.getName(), temp.getNickName()));temp = temp.next;}}
}/*** 定义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 = name;this.no = 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) {this.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、代码实现

package work.rexhao.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 = sc1.nextLine();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 = sc1.nextLine();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 = sc1.nextLine();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 = head.next;while (temp != null) {ans++;temp = temp.next;}return ans;}/*** 插入*/public void add(stuNode sn) {if (head.next == null) {head.next = sn;sn.pre = head;return;}stuNode temp = head.next;while (true) {if (temp.next == null) {break;}temp = temp.next;}temp.next = sn;sn.pre = temp;}/*** 遍历*/public void show() {if (head.next == null) {System.out.println("单链表为空");return;}stuNode temp = head.next;while (temp != null) {System.out.println(temp);temp = temp.next;}}/*** 修改*/public void change(stuNode sn) {if (head.next == null) {System.out.println("单链表为空");return;}stuNode temp = head.next;while (temp != null) {if (temp.getNo() == sn.getNo()) {temp.setName(sn.getName());temp.setNo(sn.getNo());return;}temp = temp.next;}System.out.printf("未找到no=%d的节点\n", sn.getNo());}/*** 自我删除*/public void delete(int no) {if (head.next == null) {System.out.println("链表为空");return;}stuNode temp = head.next;while (temp != null) {if (temp.getNo() == no) {/** 找到了*/temp.pre.next = temp.next;if (temp.next != null) {temp.next.pre = temp.pre;}return;}temp = temp.next;}System.out.printf("未找到no=%d的节点\n", no);}/*** 按照编号添加*/public void addByNo(stuNode sn) {/** 判空*/if (head.next == null) {head.next = sn;sn.pre = head;return;}/** 判同*/stuNode temp = head.next;while (temp != null) {if (temp.getNo() == sn.getNo()) {System.out.println("编号相同");return;}temp = temp.next;}/** 找位置添加——第一个位置*/if (sn.getNo() < head.next.getNo()) {sn.next = head.next;head.next = sn;sn.pre = head;sn.next.pre = sn;return;}/** 找位置添加——不是第一个位置*/temp = head.next;while (temp != null) {if (temp.next == null) {temp.next = sn;sn.pre = temp;return;}if (temp.getNo() < sn.getNo() && temp.next.getNo() > sn.getNo()) {sn.next = temp.next;temp.next = sn;sn.pre = head;sn.next.pre = sn;return;}temp = temp.next;}}
}/*** 定义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 = name;this.no = no;}public int getNo() {return no;}/*** 重写toString*/@Overridepublic String toString() {return "[no=" + no + ", name=" + name + "]";// 使用双向链表，不能打印next和pre}public void setNo(int no) {this.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、代码实现

package work.rexhao.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.delete(temp.getNum());j = 1;temp = temp.next;continue;}j++;temp = temp.next;}csll.show();}
}class circleSingleLinkedList {public Node head = null;/*** 添加节点*/public void add(Node n) {/** 空链表，直接放后面*/if (head == null) {head = n;n.next = head;return;}/** 非空，遍历加在后面*/Node temp = head;while (temp.next != head) {temp = temp.next;}temp.next = n;n.next = head;}/*** 遍历*/public void show() {Node temp = head;boolean loop = true;while (loop) {System.out.println(temp);temp = temp.next;if (temp == head) {loop = false;}}}/*** 有效元素*/public int usedNode() {if (head == null) {return 0;}if (head.next == head) {return 1;}Node temp = head;int ans = 1;while (temp.next != head) {temp = temp.next;ans++;}return ans;}/*** 删除节点*/public void delete(int num) {/** 判空*/if (head == null) {System.out.println("链表为空");return;}/** 删除head节点*/if (head.getNum() == num) {if (head.next == head) {/** 只有一个head*/head = null;} else {/** 还有其他节点*/// 1.改最后的nextNode temp = head;while (true) {if (temp.next == head) {temp.next = head.next;break;}temp = temp.next;}// 2.改headhead = head.next;}return;}/** 删除其他的节点*/Node temp = head.next;while (true) {if (temp.next.getNum() == num) {temp.next = temp.next.next;return;}temp = temp.next;}}
}class Node {private int num;public Node next;Node(int num, Node next) {this.num = num;this.next = next;}Node(int num) {this.num = num;this.next = null;}@Overridepublic String toString() {return "Node[num=" + num + "]";}public int getNum() {return num;}public void setNum(int num) {this.num = num;}}

---

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

本文标签： 韩顺平