链表介绍

链表是有序的列表，但是它在内存中是存储结构如左下，逻辑结构如右下：
image.pngimage.png

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

    单链表的应用实例

    使用带 head 头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作。 这里分两种实现，一种按排名插入，一种直接插入到链表尾部；

前提

  • head 头节点不保存任何数据，只是为了找到链表的第一个元素；
  • 在遍历时要保持 head 节点不改变，目的是不丢失链表头。

  • 遍历时创建一个临时变量代替 head 节点遍历整个链表。

    • 创建临时变量代表 head 头节点；
    • 使用临时变量依次指向 next 节点完成遍历；

      1. 直接尾部插入

      分析：

  • 直接尾部插入：

    • 先创建一个 head 头节点，表示单链表的头，不可移动；
    • 找到链表中最后一个元素；（需要遍历，使用临时变量代替 head 节点遍历）
    • 将最后一个元素的 next 指向要插入的元素；
  • 遍历时：为了保证 head 头节点保持不动，需要一个辅助变量来循环遍历链表；

    实现：

    水浒英雄节点类

    ```java package com.zsy.datastructure.linkedlist;

/**

  • @author zhangshuaiyin */ public class HeroNode {

    int no; String name; String nickName; HeroNode next;

    public HeroNode(int no, String name, String nickName) {

    1.  this.no = no;
    2.  this.name = name;
    3.  this.nickName = nickName;

    }

    @Override public String toString() {

    1.  if (next == null) {
    2.      return "HeroNode{" +
    3.              "no=" + no +
    4.              ", name='" + name + '\'' +
    5.              ", nickName='" + nickName + '\'' +
    6.              ", next=" + next +
    7.              '}';
    8.  } else {
    9.      return "HeroNode{" +
    10.              "no=" + no +
    11.              ", name='" + name + '\'' +
    12.              ", nickName='" + nickName + '\'' +
    13.              '}';
    15.  }

    } } ```

    单链表实现（尾部新增+遍历）

    ```java package com.zsy.datastructure.linkedlist;

/**

  • @author zhangshuaiyin */ public class SingleLinkedList {

    private final HeroNode head = new HeroNode(0, “”, “”);

    public void add(HeroNode node) {

    1.  HeroNode temp = head;
    2.  while (temp.next != null) {
    3.      temp = temp.next;
    4.  }
    5.  temp.next = node;

    }

    public void list() {

    1.  if (head.next == null) {
    2.      throw new RuntimeException("当前链表为空");
    3.  }
    4.  HeroNode temp = head.next;
    5.  while (temp != null) {
    6.      System.out.println(temp);
    7.      temp = temp.next;
    8.  }

    } } ```

    测试

    ```java package com.zsy.datastructure.linkedlist;

/**

  • @author zhangshuaiyin */ public class SingleLinkedListTest { public static void main(String[] args) {

    1.  HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    2.  HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    3.  HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    4.  HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    6.  SingleLinkedList linkedList = new SingleLinkedList();
    7.  linkedList.add(hero1);
    8.  linkedList.add(hero4);
    9.  linkedList.add(hero2);
    10.  linkedList.add(hero3);
    12.  linkedList.list();

    } } ```

    2. 根据编号大小插入

    分析：

  • 创建 temp 临时节点代替 head 遍历链表，找到插入位置 temp.next；
  • 遍历时要判断编号不能重复，如果重复，提示错误信息；

  • 插入步骤：new.next = temp.next; temp.next = new;

    实现：按编号大小插入方法

    1. /**
    2. * 按照编号由小到大的顺序插入节点，编号不可重复
    3. *
    4. * @param node 插入节点
    5. */
    6. public void addByOrder(HeroNode node) {
    7.   HeroNode temp = head;
    8.   while (temp.next != null) {
    9.       if (temp.next.no == node.no) {
    10.           System.out.printf("编号 %d 已存在，插入失败\n", node.no);
    11.           return;
    12.       } else if (temp.next.no > node.no) {
    13.           // 此时说明新节点应该插入 temp 的下一个位置
    14.           break;
    15.       }
    16.       temp = temp.next;
    17.   }
    18.   node.next = temp.next;
    19.   temp.next = node;
    20. }

    3. 根据编号修改

    分析：

  • 创建 temp 临时节点代替 head 遍历链表，找到要修改的节点 temp；

  • 修改操作：temp.name = node.name; temp.nickName = node.nickName;

    实现：

    1. /**
    2. * 根据新节点信息修改链表中相同编号的节点
    3. *
    4. * @param node 新节点
    5. */
    6. public void update(HeroNode node) {
    7.   HeroNode temp = head;
    8.   while (temp.next != null) {
    9.       temp = temp.next;
    10.       if (temp.no == node.no) {
    11.           temp.name = node.name;
    12.           temp.nickName = node.nickName;
    13.           return;
    14.       }
    15.   }
    16.   System.out.printf("没有找到编号是 %d 的节点，不能修改\n", node.no);
    17. }

    4. 根据编号删除

    分析：

  • 创建 temp 临时节点代替 head 遍历链表，找到要删除的节点 temp.next（temp 是要删除节点的前一个节点）；

  • 删除操作：temp.next = temp.next.next;

    实现：

    1. /**
    2. * @param no 根据编号 no 删除链表中对应的节点
    3. */
    4. public void delete(int no) {
    5.   HeroNode temp = head;
    6.   while (temp.next != null) {
    7.       if (temp.next.no == no) {
    8.           temp.next = temp.next.next;
    9.           return;
    10.       }
    11.       temp = temp.next;
    12.   }
    13.   System.out.printf("没有找到编号是 %d 的节点，不能修改\n", no);
    14. }

    面试题实现

    求单链表中有效节点的个数

    1. /**
    2. * 获取单链表有效节点个数
    3. *
    4. * @return 有效节点数
    5. */
    6. public int getLength() {
    7.   HeroNode temp = head;
    8.   int length = 0;
    9.   while (temp.next != null) {
    10.       length++;
    11.       temp = temp.next;
    12.   }
    13.   return length;
    14. }

    查找单链表中的倒数第 k 个结点 【新浪面试题】

    分析：

  • 首先遍历获取链表有效节点个数 size；

  • 然后再次遍历 size-k+1 次，即找到倒数第 k 个节点（+1是因为下标从0开始）
  • 四个数，倒数第一就是整数第四(4-1+1)；倒数第二就是整数第三(4-2+1)
    1. /**
    2. * 查找单链表中的倒数第 k 个结点
    3. *
    4. * @param k 倒数第 k 个
    5. * @return 找得到返回节点对象，找不到返回 null
    6. */
    7. public HeroNode getLastIndexNode(int k) {
    8.   HeroNode temp = head;
    9.   int size = getLength();
    10.   // 空链表返回空
    11.   if (temp.next == null || k > size || k <= 0) {
    12.       return null;
    13.   }
    14.   // 比如 size = 3; k = 2; i =1 找第二个(下标是1)
    15.   temp = temp.next;
    16.   for (int i = 0; i < size - k; i++) {
    17.       temp = temp.next;
    18.   }
    19.   return temp;
    20. }

    单链表的反转【腾讯面试题】

    参考 ：https://www.cnblogs.com/keeya/p/9218352.html

分析：

  • 定义 reverseHead 作为反转链表的头；
  • 遍历原来的链表，从头依次取出元素，然后添加到反转链表的头节点后面(添加到最前面)

  • 操作： head.next = reverseHead.next

    1. /**
    2. * 单链表的反转
    3. * 1. 创建一个新的头节点用于保存反转后的链表
    4. * 2. 遍历原来的链表，依次取出元素放置新头节点的后面
    5. */
    6. public void reverse() {
    7.   if (head.next == null || head.next.next == null) {
    8.       return;
    9.   }
    11.  // 反转后链表头节点
    12.   HeroNode revereHead = new HeroNode(0, "", "");
    14.   // 遍历用辅助节点
    15.   HeroNode temp = head.next;
    17.   // 取出节点的下一个节点，保存遍历指针
    18.   HeroNode next = null;
    19.   while (temp != null) {
    20.       // 标记下一个元素，此时temp节点就是取出的节点
    21.       next = temp.next;
    23.       // 将反转链表节点放到取出的第一个节点后面
    24.       temp.next = revereHead.next;
    26.       // 将取出的节点（包含反转链表的节点）放到反转链表第一个位置
    27.       revereHead.next = temp;
    29.       // 辅助节点后移
    30.       temp = next;
    31.   }
    32.   head.next = revereHead.next;
    33. }

    从尾到头打印单链表【百度面试题】

    分析：

  1. 可以先将单链表反转再打印链表，但是会破坏单链表的结构，不推荐；
  2. 使用栈先进后出的特性实现逆序打印单链表；
    1. /**
    2. * 逆序打印链表信息(栈)
    3. */
    4. public void reverseList() {
    5.  if (head.next == null) {
    6.      throw new RuntimeException("当前链表为空");
    7.  }
    8.  HeroNode temp = head.next;
    9.  Stack<HeroNode> stack = new Stack<>();
    10.  while (temp != null) {
    11.      stack.push(temp);
    12.      temp = temp.next;
    13.  }
    14.  while (stack.size() > 0) {
    15.      System.out.println(stack.pop());
    16.  }
    17. }

    合并两个有序的单链表，合并之后的链表依然有序

    分析：
  • 创建临时头节点保存合并后的节点信息；
  • 同时遍历两个单链表，根据条件比较大小；
  • 较小的节点放到临时头节点的后面即可；

  • 其中一个单链表遍历结束，另一个单链表剩余的数据直接添加到最后；

    1. /**
    2. * 合并两个有序的单链表，合并之后的链表依然有序
    3. *
    4. * @param linkedList 要合并的单链表
    5. */
    6. public void mergeWithOrder(SingleLinkedList linkedList) {
    7.   HeroNode otherHead = linkedList.head;
    8.   if (head.next == null && otherHead.next == null) {
    9.       throw new RuntimeException("要合并的两个链表为空~");
    10.   } else if (head.next == null) {
    11.       head.next = otherHead.next;
    12.   } else if (otherHead.next == null) {
    13.       return;
    14.   }
    16.   // 保存合并后链表的头节点
    17.   HeroNode node = new HeroNode(0, "", "");
    18.   HeroNode temp0 = node;
    20.   HeroNode temp1 = head.next;
    21.   HeroNode temp2 = otherHead.next;
    23.   // 同时遍历两个有序单链表
    24.   while (temp1 != null && temp2 != null) {
    25.       // 遍历两个链表，比较编号大小，比较小的放到合并链表的最后
    26.       if (temp1.no < temp2.no) {
    27.           temp0.next = temp1;
    28.           temp1 = temp1.next;
    29.       } else {
    30.           temp0.next = temp2;
    31.           temp2 = temp2.next;
    32.       }
    33.       // 合并后链表的辅助节点后移
    34.       temp0 = temp0.next;
    35.   }
    36.   // 当有链表遍历结束，直接将另一个链表剩余的数据放到最后
    37.   if (temp1 == null) {
    38.       temp0.next = temp2;
    39.   }
    40.   if (temp2 == null) {
    41.       temp0.next = temp1;
    42.   }
    43.   // 返回合并后链表的头节点
    44.   head.next = node.next;
    45. }