1、链表概念及应用

1.1、概念

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

1.2、链表应用-增删改查

使用带head头的单向链表实现 –水浒英雄排行榜管理
1、完成对英雄人物的增删改查操作， 注: 删除和修改,查找
可以考虑学员独立完成，也可带学员完成
2、第一种方法在添加英雄时，直接添加到链表的尾部
3、第二种方式在添加英雄时，根据排名将英雄插入到指定位置 (如果有这个排名，则添加失败，并给出提示)

1.2.1、data类

  1. public class Data {
  2.     private int no;
  3.     private String name;
  4.     private String nickName;
  6.     public Data(int no, String name, String nickName) {
  7.         this.no = no;
  8.         this.name = name;
  9.         this.nickName = nickName;
  10.     }
  12.     public Data() {
  13.     }
  15.     public int getNo() {
  16.         return no;
  17.     }
  19.     public void setNo(int no) {
  20.         this.no = no;
  21.     }
  23.     public String getName() {
  24.         return name;
  25.     }
  27.     public void setName(String name) {
  28.         this.name = name;
  29.     }
  31.     public String getNickName() {
  32.         return nickName;
  33.     }
  35.     public void setNickName(String nickName) {
  36.         this.nickName = nickName;
  37.     }
  39.     @Override
  40.     public String toString() {
  41.         return "Data{" +
  42.                 "no=" + no +
  43.                 ", name='" + name + '\'' +
  44.                 ", nickName='" + nickName + '\'' +
  45.                 '}';
  46.     }
  47. }

1.2.2、Node类

  1. public class Node {
  2.     private Data data;
  3.     private Node next;
  5.     public Node() {
  6.     }
  8.     public Node(Data data) {
  9.         this.data = data;
  10.     }
  11.     public Node(Data data,Node next) {
  12.         this.data = data;
  13.         this.next=next;
  14.     }
  16.     public Data getData() {
  17.         return data;
  18.     }
  20.     public void setData(Data data) {
  21.         this.data = data;
  22.     }
  24.     public Node getNext() {
  25.         return next;
  26.     }
  28.     public void setNext(Node next) {
  29.         this.next = next;
  30.     }
  32.     @Override
  33.     public String toString() {
  34.         return "Node{" +
  35.                 "data=" + data +
  36.                 '}';
  37.     }
  38. }

1.2.3、SingleLinkedList类

  1. public class SingleLinkedList {
  3.     private Node head=new Node(null,null);
  5.     public void setHead(Node head){
  6.         this.head=head;
  7.     }
  8.     public Node getHead(){
  9.         return head;
  10.     }
  12.     //添加节点，不考虑排序
  13.     public void insertNode(Node node){
  14.         if(node.getData()==null) System.out.println("无效的节点");
  16.         if(head.getNext()==null){
  17.             head.setNext(node);
  18.             System.out.println("添加结点成功");
  19.             return;
  20.         }
  21.         Node temp=head;
  22.         while (true){
  23.             if(temp.getNext()==null){
  24.                 temp.setNext(node);
  25.                 System.out.println("添加结点成功");
  26.                 break;
  27.             }
  28.             temp=temp.getNext();
  29.         }
  30.     }
  32.     //排序添加节点且不允许相同no的节点
  33.     public void insertNodeByOrder(Node node){
  35.         if(node.getData()==null) System.out.println("无效的节点");
  37.         if(head.getNext()==null){
  38.             head.setNext(node);
  39.             return;
  40.         }
  41.         Node temp=head;
  42.         while(true){
  43.             if(temp.getNext()==null){
  44.                 temp.setNext(node);
  45.                 break;
  46.             }else if(temp.getNext().getData().getNo()==node.getData().getNo()){
  47.                 System.out.println("存在相同编号的节点"+temp.getNext());
  48.                 break;
  49.             }else if(temp.getNext().getData().getNo()>node.getData().getNo()){
  50.                 node.setNext(temp.getNext());
  51.                 temp.setNext(node);
  52.                 break;
  53.             }
  54.             temp=temp.getNext();
  55.         }
  56.     }
  58.     //通过编号修改昵称
  59.     public void updateNodeByNo(int no,String nickName){
  60.         if(head.getNext()==null){
  61.             System.out.println("链表为空");
  62.             return;
  63.         }
  64.         Node temp=head;
  65.         while(true){
  66.             if(temp.getNext()==null){
  67.                 System.out.println("没有找到该编号的节点信息");
  68.                 break;
  69.             }else if(temp.getNext().getData().getNo()==no){
  70.                 temp.getNext().getData().setNickName(nickName);
  71.                 break;
  72.             }
  73.             temp=temp.getNext();
  74.         }
  75.     }
  77.     //通过编号删除节点
  78.     public void deleteNode(int no){
  79.         if(head.getNext()==null){
  80.             System.out.println("链表为空");
  81.             return;
  82.         }
  83.         Node temp=head;
  84.         while(true){
  85.             if(temp.getNext()==null){
  86.                 System.out.println("没有找到该编号的节点");
  87.                 break;
  88.             }else if(temp.getNext().getData().getNo()==no) {
  89.                 temp.setNext(temp.getNext().getNext());
  90.                 break;
  91.             }
  92.             temp=temp.getNext();
  93.         }
  94.     }
  96.     //获取链表的长度
  97.     public int getLength(){
  98.         if(head.getNext()==null){
  99.             System.out.println("链表为空");
  100.             System.exit(0);
  101.         }
  102.         Node temp=head;
  103.         int result=0;
  104.         while (true){
  105.             if(temp.getNext()==null){
  106.                 break;
  107.             }
  108.             result++;
  109.             temp=temp.getNext();
  110.         }
  111.         return result;
  112.     }
  114.     //打印链表节点
  115.     public void printNode(){
  116.         if(head.getNext()==null){
  117.             System.out.println("链表为空");
  118.             return;
  119.         }
  120.         Node temp=head;
  121.         while (true){
  122.             if(temp.getNext()==null){
  123.                 break;
  124.             }
  125.             temp=temp.getNext();
  126.             System.out.println(temp);
  127.         }
  128.     }
  130. }

2、单链表面试题

单链表的常见面试题有如下:
1、求单链表中有效节点的个数
2、查找单链表中的倒数第k个结点 【新浪面试题】
3、单链表的反转【腾讯面试题，有点难度】
4、从尾到头打印单链表 【百度，要求方式1：反向遍历 。 方式2：Stack栈】
5、合并两个有序的单链表，合并之后的链表依然有序【课后练习.】

2.1、新浪-找到单数第k个节点

  1. //查找链表倒数第index个元素
  2.     public static Node getLastIndexNode(Node head, int index) {
  3.         if (head.getNext() == null) {
  4.             System.out.println("链表为空");
  5.             return null;
  6.         }
  8.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  9.         singleLinkedList.setHead(head);
  10.         int length = singleLinkedList.getLength();
  12.         if (index <= 0 || index > length) return null;
  14.         Node temp=head;
  15.         int curNodeIndex=0;
  16.         while(true){
  17.            if(curNodeIndex==(length-index)+1){
  18.                return temp;
  19.            }
  20.            temp=temp.getNext();
  21.             curNodeIndex++;
  22.         }
  23.     }

2.2、腾讯-反转链表

  1. //反转链表,头插法
  2.     public static void reverseLinkedList(Node head){
  3.         if(head.getNext()==null){
  4.             System.out.println("空链表");
  5.             return;
  6.         }
  7.         if(head.getNext().getNext()==null){
  8.             System.out.println("当前链表不需要进行反转");
  9.             return;
  10.         }
  12.         Node curNode=head.getNext();
  13.         Node nextNode=head.getNext().getNext();
  14.         curNode.setNext(null);
  15.         head.setNext(curNode);
  16.         while(true){
  17.            if(nextNode==null){
  18.                return;
  19.            }
  20.            curNode=nextNode;
  21.            nextNode=nextNode.getNext();
  22.            curNode.setNext(head.getNext());
  23.            head.setNext(curNode);
  24.         }
  25.     }

2.3、百度-从尾到头打印链表

  1.  //从为到头打印链表
  2.     public static void printNodeFromTailToHead(Node head){
  3.         if(head.getNext()==null){
  4.             System.out.println("空链表");
  5.             return;
  6.         }
  7.         if(head.getNext().getNext()==null){
  8.             System.out.println(head.getNext());
  9.             return;
  10.         }
  11.         SingleLinkedList singleLinkedList = new SingleLinkedList();
  12.         singleLinkedList.setHead(head);
  13.         int length = singleLinkedList.getLength();
  15.         Node[] nodes=new Node[length];
  16.         int cur=length-1;
  18.         Node temp=head;
  19.         while(true){
  20.             if (temp.getNext()==null){
  21.                 break;
  22.             }
  23.             temp=temp.getNext();
  24.             nodes[cur--]=temp;
  25.         }
  26.         for (Node node : nodes) {
  27.             System.out.println(node);
  28.         }
  29.     }

2.4、合并链表并保持有序

3、双向链表-增删改查

image.png

3.1、Node类

  1. public class Node {
  2.     private Data data;
  3.     private Node next;
  4.     private Node pre;
  6.     public Node() {
  7.     }
  9.     public Node(Data data) {
  10.         this.data = data;
  11.     }
  12.     public Node(Data data,Node next) {
  13.         this.data = data;
  14.         this.next=next;
  15.     }
  17.     public Data getData() {
  18.         return data;
  19.     }
  21.     public void setData(Data data) {
  22.         this.data = data;
  23.     }
  25.     public Node getPre() {
  26.         return pre;
  27.     }
  29.     public void setPre(Node pre) {
  30.         this.pre = pre;
  31.     }
  33.     public Node getNext() {
  34.         return next;
  35.     }
  37.     public void setNext(Node next) {
  38.         this.next = next;
  39.     }
  41.     @Override
  42.     public String toString() {
  43.         return "Node{" +
  44.                 "data=" + data +
  45.                 '}';
  46.     }
  47. }

3.2、DoubleLinkedList类-增删改查

  1. public class DoubleLinkedList {
  2.     private Node head=new Node(null,null);
  3.     private Node pre;
  4.     private Node next;
  6.     public Node getHead() {
  7.         return head;
  8.     }
  10.     public void setHead(Node head) {
  11.         this.head = head;
  12.     }
  14.     public Node getPre() {
  15.         return pre;
  16.     }
  18.     public void setPre(Node pre) {
  19.         this.pre = pre;
  20.     }
  22.     public Node getNext() {
  23.         return next;
  24.     }
  26.     public void setNext(Node next) {
  27.         this.next = next;
  28.     }
  30.     @Override
  31.     public String toString() {
  32.         return "DoubleLinkedList{" +
  33.                 "head=" + head +
  34.                 ", pre=" + pre +
  35.                 ", next=" + next +
  36.                 '}';
  37.     }
  39.     //插入节点,不允许相同节点且排序
  40.     public void insertNode(Node node){
  41.         if(node.getData()==null||node==null)return;
  43.         if(head.getNext()==null){
  44.             head.setNext(node);
  45.             node.setPre(head);
  46.             return;
  47.         }
  49.         Node temp=head;
  50.         while(true){
  51.             if(temp.getNext()==null){
  52.                 temp.setNext(node);
  53.                 node.setPre(temp);
  54.                 break;
  55.             }else if(temp.getNext().getData().getNo()>node.getData().getNo()){
  56.                 node.setNext(temp.getNext());
  57.                 temp.getNext().setPre(node);
  58.                 temp.setNext(node);
  59.                 break;
  60.             }else if(temp.getNext().getData().getNo()==node.getData().getNo()){
  61.                 System.out.println("存在相同编号的节点，无法添加"+temp.getNext());
  62.                 break;
  63.             }
  64.             temp=temp.getNext();
  65.         }
  66.     }
  68.     //根据id更新昵称信息
  69.     public void updateNodeByNo(int no,String nickName){
  70.         if(head.getNext()==null){
  71.             System.out.println("链表为空");
  72.             return;
  73.         }
  74.         Node temp=head;
  75.         while(true){
  76.             if(temp.getNext()==null){
  77.                 System.out.println("没有找到该编号的节点信息");
  78.                 break;
  79.             }else if(temp.getNext().getData().getNo()==no){
  80.                 temp.getNext().getData().setNickName(nickName);
  81.                 break;
  82.             }
  83.             temp=temp.getNext();
  84.         }
  85.     }
  87.     //根据id删除节点
  88.     public void deleteNode(int no){
  89.         if(head.getNext()==null){
  90.             System.out.println("链表为空");
  91.             return;
  92.         }
  93.         Node temp=head;
  94.         while(true){
  95.             if(temp.getNext()==null){
  96.                 System.out.println("没有找到该编号的节点");
  97.                 break;
  98.             }else if(temp.getNext().getData().getNo()==no) {
  99.                 temp.getNext().getNext().setPre(temp);
  100.                 temp.setNext(temp.getNext().getNext());
  101.                 break;
  102.             }
  103.             temp=temp.getNext();
  104.         }
  105.     }
  107.     //打印双向链表
  108.     public void printDoubleList(){
  109.         if(head.getNext()==null){
  110.             System.out.println("链表为空");
  111.             return;
  112.         }
  113.         Node temp=head;
  114.         while (true){
  115.             if(temp.getNext()==null){
  116.                 break;
  117.             }
  118.             temp=temp.getNext();
  119.             System.out.println(temp);
  120.         }
  121.     }
  122. }

4、环形链表-增删改查

image.png
Josephu 问题
Josephu 问题为：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。
提示
用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。