第 4 章链表（二）-阿里云开发者社区

3.2、查找单链表中的倒数第 k 个结点

3.2.1、代码思路

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

首先，获取整个链表中元素的个数 size

在使用 for 循环定位至倒数第 index（形参）个节点，返回即可

for 循环的条件应如何确定？for (int i = 0; i < x; i++) 中 x 的值应是多少？我们需要定位至倒数第 index 个节点，在 for 循环之前，我们已经定位置首节点，还需再走 (size - index ) 步，定位至倒数第 index 个节点

举例说明：链表中一共有 4 个元素，想要定位至倒数第 2 个节点，那么需要在首节点之后走两步，到达倒数第 2 个节点

3.2.2、代码实现

查找单链表中的倒数第k个结点

// 查找单链表中的倒数第k个结点 【新浪面试题】
// 思路
// 1. 编写一个方法，接收head节点，同时接收一个index
// 2. index 表示是倒数第index个节点
// 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
// 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
// 5. 如果找到了，则返回该节点，否则返回nulll
public static HeroNode findLastIndexNode(HeroNode head, int index) {
    // 判断如果链表为空，返回null
    if (head.next == null) {
        return null;// 没有找到
    }
    // 第一个遍历得到链表的长度(节点个数)
    int size = getLength(head);
    // 第二次遍历 size-index 位置，就是我们倒数的第K个节点
    // 先做一个index的校验
    if (index <= 0 || index > size) {
        return null;
    }
    // 定义给辅助变量， for 循环定位到倒数的index
    HeroNode cur = head.next; // 3 // 3 - 1 = 2
    for (int i = 0; i < size - index; i++) {
        cur = cur.next;
    }
    return cur;
}

测试代码

public static void main(String[] args) {
    // 进行测试
    // 先创建节点
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    // 创建要给链表
    SingleLinkedList singleLinkedList = new SingleLinkedList();
    // 加入
    singleLinkedList.add(hero1);
    singleLinkedList.add(hero2);
    singleLinkedList.add(hero3);
    singleLinkedList.add(hero4);
    singleLinkedList.list();
    // 测试一下看看是否得到了倒数第K个节点
    HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 2);
    System.out.println("res=" + res);
}

程序运行结果

HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
res=HeroNode [no=3, name=吴用, nickName=智多星]

3.3、单链表的反转

3.3.1、代码思路

单链表的反转【腾讯面试题，有点难度】

定义一个新的头结点 reverseHead ，一点一点将链表反转后，再串起来

怎么个串法？

在原链表中每读取一个节点（cur），先保存其下一个节点的地址（next），然后将 cur 节点放在新链表的最前面

然后执行遍历：cur = next ，即指针后移

遍历完成后，新链表即是反转后的链表

如何将 cur 节点插入在新链表的最前面

cur.next = reverseHead.next;

reverseHead.next = cur;

while 循环终止条件？ cur == null ：已遍历至链表尾部

单链表的翻转可以参考我的这篇博文：https://blog.csdn.net/oneby1314/article/details/107577923

3.3.2、代码实现

单链表的反转

// 将单链表反转
public static void reversetList(HeroNode head) {
    // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }
    // 定义一个辅助的指针(变量)，帮助我们遍历原来的链表
    HeroNode cur = head.next;
    HeroNode next = null;// 指向当前节点[cur]的下一个节点
    HeroNode reverseHead = new HeroNode(0, "", "");
    // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
    // 动脑筋
    while (cur != null) {
        next = cur.next;// 先暂时保存当前节点的下一个节点，因为后面需要使用
        cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的最前端
        reverseHead.next = cur; // 将cur 连接到新的链表上
        cur = next;// 让cur后移
    }
    // 将head.next 指向 reverseHead.next , 实现单链表的反转
    head.next = reverseHead.next;
}

测试代码

public static void main(String[] args) {
    // 进行测试
    // 先创建节点
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    // 创建要给链表
    SingleLinkedList singleLinkedList = new SingleLinkedList();
    // 加入
    singleLinkedList.add(hero1);
    singleLinkedList.add(hero2);
    singleLinkedList.add(hero3);
    singleLinkedList.add(hero4);
    // 测试一下单链表的反转功能
    System.out.println("原来链表的情况~~");
    singleLinkedList.list();
    System.out.println("反转单链表~~");
    reversetList(singleLinkedList.getHead());
    singleLinkedList.list();
}

程序运行结果

原来链表的情况~~
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
反转单链表~~
HeroNode [no=4, name=林冲, nickName=豹子头]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=1, name=宋江, nickName=及时雨]

3.4、单链表的反转（我的代码）

3.4.1、代码思路

单链表的反转【腾讯面试题，有点难度】

原链表为 cur 指向 next ，反转链表不就是把 next 指向 cur 吗？

由于 next 指向 cur 时，next 将丢失其下一节点的地址，所以需要先将 nnext 保存起来

next ==null 时链表已经反转完毕，最后将头结点指向 cur 节点即可

3.4.2、代码实现

单链表的反转

// 将单链表反转
public static void myReversetList(HeroNode head) {
    // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
    if (head.next == null || head.next.next == null) {
        return;
    }
    // 当前节点
    HeroNode cur = head.next; 
    // 下一节点
    HeroNode next = cur.next; 
    // 首节点反转后为尾节点，需指向 null
    cur.next = null;
    // next == null 时，链表已经反转完毕
    while (next != null) {
        // 记录 next 的后一节点
        HeroNode nnext = next.next;
        // 反转链表
        next.next = cur;
        // 指针后移
        cur = next;
        next = nnext;
    }
    // 最后加上首节点
    head.next = cur;
}

测试代码

public static void main(String[] args) {
    // 进行测试
    // 先创建节点
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    // 创建要给链表
    SingleLinkedList singleLinkedList = new SingleLinkedList();
    // 加入
    singleLinkedList.add(hero1);
    singleLinkedList.add(hero2);
    singleLinkedList.add(hero3);
    singleLinkedList.add(hero4);
    // 测试一下单链表的反转功能
    System.out.println("原来链表的情况~~");
    singleLinkedList.list();
    System.out.println("反转单链表~~");
    reversetList(singleLinkedList.getHead());
    singleLinkedList.list();
}

程序运行结果

原来链表的情况~~
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
反转单链表~~
HeroNode [no=4, name=林冲, nickName=豹子头]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=1, name=宋江, nickName=及时雨]

3.5、从尾到头打印单链表

3.5.1、栈的基本使用

测试代码

public static void main(String[] args) {
    Stack<String> stack = new Stack();
    // 入栈
    stack.add("jack");
    stack.add("tom");
    stack.add("smith");
    // 出栈
    // smith, tom , jack
    while (stack.size() > 0) {
        System.out.println(stack.pop());//pop就是将栈顶的数据取出
    }
}

程序运行结果

smith
tom
jack

3.5.2、代码思路

从尾到头打印单链表【百度，要求方式1：反向遍历。方式2：Stack栈】

方式一：先将单链表进行反转操作，然后再遍历输出，问题：破坏原链表结构，不可取
方式二：遍历链表，去除节点压入栈中，利用栈先进后出的特点，实现逆序打印

3.5.3、代码实现

从尾到头打印单链表

// 方式2：
// 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
public static void reversePrint(HeroNode head) {
    if (head.next == null) {
        return;// 空链表，不能打印
    }
    // 创建要给一个栈，将各个节点压入栈
    Stack<HeroNode> stack = new Stack<HeroNode>();
    HeroNode cur = head.next;
    // 将链表的所有节点压入栈
    while (cur != null) {
        stack.push(cur);
        cur = cur.next; // cur后移，这样就可以压入下一个节点
    }
    // 将栈中的节点进行打印,pop 出栈
    while (stack.size() > 0) {
        System.out.println(stack.pop()); // stack的特点是先进后出
    }
}

测试代码

public static void main(String[] args) {
    //进行测试
    //先创建节点
    HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
    HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
    HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
    HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
    //创建要给链表
    SingleLinkedList singleLinkedList = new SingleLinkedList();
    //加入
    singleLinkedList.add(hero1);
    singleLinkedList.add(hero2);
    singleLinkedList.add(hero3);
    singleLinkedList.add(hero4);
    System.out.println("原来链表的情况~~");
    singleLinkedList.list();
    System.out.println("测试逆序打印单链表, 没有改变链表的结构~~");
    reversePrint(singleLinkedList.getHead());
}

程序运行结果

原来链表的情况~~
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
测试逆序打印单链表, 没有改变链表的结构~~
HeroNode [no=4, name=林冲, nickName=豹子头]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=1, name=宋江, nickName=及时雨]

3.6、合并两个有序的单链表

3.6.1、代码思路

合并两个有序的单链表，合并之后的链表依然有序【课后练习】

3.6.2、代码实现

合并两个有序的单链表，合并之后的链表依然有序
具体讲解见我的一篇博客：https://blog.csdn.net/oneby1314/article/details/107590876

3.7、单向链表所有代码

public class SingleLinkedListDemo {
 public static void main(String[] args) {
  //进行测试
  //先创建节点
  HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
  HeroNode hero2 = new HeroNode(2, "卢俊义", "玉麒麟");
  HeroNode hero3 = new HeroNode(3, "吴用", "智多星");
  HeroNode hero4 = new HeroNode(4, "林冲", "豹子头");
  //创建要给链表
  SingleLinkedList singleLinkedList = new SingleLinkedList();
  //加入
  singleLinkedList.add(hero1);
  singleLinkedList.add(hero4);
  singleLinkedList.add(hero2);
  singleLinkedList.add(hero3);
  // 测试一下单链表的反转功能
  System.out.println("原来链表的情况~~");
  singleLinkedList.list();
  System.out.println("反转单链表~~");
  reversetList(singleLinkedList.getHead());
  singleLinkedList.list();
  System.out.println("测试逆序打印单链表, 没有改变链表的结构~~");
  reversePrint(singleLinkedList.getHead());
  //加入按照编号的顺序
  singleLinkedList.addByOrder(hero1);
  singleLinkedList.addByOrder(hero4);
  singleLinkedList.addByOrder(hero2);
  singleLinkedList.addByOrder(hero3);
  //显示一把
  singleLinkedList.list();
  //测试修改节点的代码
  HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
  singleLinkedList.update(newHeroNode);
  System.out.println("修改后的链表情况~~");
  singleLinkedList.list();
  //删除一个节点
  singleLinkedList.del(1);
  singleLinkedList.del(4);
  System.out.println("删除后的链表情况~~");
  singleLinkedList.list();
  //测试一下 求单链表中有效节点的个数
  System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));//2
  //测试一下看看是否得到了倒数第K个节点
  HeroNode res = findLastIndexNode(singleLinkedList.getHead(), 3);
  System.out.println("res=" + res);
 }
 // 方式2：
 // 可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，就实现了逆序打印的效果
 public static void reversePrint(HeroNode head) {
  if (head.next == null) {
   return;// 空链表，不能打印
  }
  // 创建要给一个栈，将各个节点压入栈
  Stack<HeroNode> stack = new Stack<HeroNode>();
  HeroNode cur = head.next;
  // 将链表的所有节点压入栈
  while (cur != null) {
   stack.push(cur);
   cur = cur.next; // cur后移，这样就可以压入下一个节点
  }
  // 将栈中的节点进行打印,pop 出栈
  while (stack.size() > 0) {
   System.out.println(stack.pop()); // stack的特点是先进后出
  }
 }
 // 将单链表反转
 public static void reversetList(HeroNode head) {
  // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
  if (head.next == null || head.next.next == null) {
   return;
  }
  // 定义一个辅助的指针(变量)，帮助我们遍历原来的链表
  HeroNode cur = head.next;
  HeroNode next = null;// 指向当前节点[cur]的下一个节点
  HeroNode reverseHead = new HeroNode(0, "", "");
  // 遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead 的最前端
  // 动脑筋
  while (cur != null) {
   next = cur.next;// 先暂时保存当前节点的下一个节点，因为后面需要使用
   cur.next = reverseHead.next;// 将cur的下一个节点指向新的链表的最前端
   reverseHead.next = cur; // 将cur 连接到新的链表上
   cur = next;// 让cur后移
  }
  // 将head.next 指向 reverseHead.next , 实现单链表的反转
  head.next = reverseHead.next;
 }
 // 将单链表反转
 public static void myReversetList(HeroNode head) {
  // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
  if (head.next == null || head.next.next == null) {
   return;
  }
  // 当前节点
  HeroNode cur = head.next; 
  // 下一节点
  HeroNode next = cur.next; 
  // 首节点反转后为尾节点，需指向 null
  cur.next = null;
  // next == null 时，链表已经反转完毕
  while (next != null) {
   // 记录 next 的后一节点
   HeroNode nnext = next.next;
   // 反转链表
   next.next = cur;
   // 指针后移
   cur = next;
   next = nnext;
  }
  // 最后加上头结点
  head.next = cur;
 }
 // 查找单链表中的倒数第k个结点 【新浪面试题】
 // 思路
 // 1. 编写一个方法，接收head节点，同时接收一个index
 // 2. index 表示是倒数第index个节点
 // 3. 先把链表从头到尾遍历，得到链表的总的长度 getLength
 // 4. 得到size 后，我们从链表的第一个开始遍历 (size-index)个，就可以得到
 // 5. 如果找到了，则返回该节点，否则返回nulll
 public static HeroNode findLastIndexNode(HeroNode head, int index) {
  // 判断如果链表为空，返回null
  if (head.next == null) {
   return null;// 没有找到
  }
  // 第一个遍历得到链表的长度(节点个数)
  int size = getLength(head);
  // 第二次遍历 size-index 位置，就是我们倒数的第K个节点
  // 先做一个index的校验
  if (index <= 0 || index > size) {
   return null;
  }
  // 定义给辅助变量， for 循环定位到倒数的index
  HeroNode cur = head.next; // 3 // 3 - 1 = 2
  for (int i = 0; i < size - index; i++) {
   cur = cur.next;
  }
  return cur;
 }
 // 方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
 /**
  * 
  * @param head 链表的头节点
  * @return 返回的就是有效节点的个数
  */
 public static int getLength(HeroNode head) {
  if (head.next == null) { // 空链表
   return 0;
  }
  int length = 0;
  // 定义一个辅助的变量, 这里我们没有统计头节点
  HeroNode cur = head.next;
  while (cur != null) {
   length++;
   cur = cur.next; // 遍历
  }
  return length;
 }
}
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList {
 // 先初始化一个头节点, 头节点不要动, 不存放具体的数据
 private HeroNode head = new HeroNode(0, "", "");
 // 返回头节点
 public HeroNode getHead() {
  return head;
 }
 // 添加节点到单向链表
 // 思路，当不考虑编号顺序时
 // 1. 找到当前链表的最后节点
 // 2. 将最后这个节点的next 指向 新的节点
 public void add(HeroNode heroNode) {
  // 因为head节点不能动，因此我们需要一个辅助遍历 temp
  HeroNode temp = head;
  // 遍历链表，找到最后
  while (true) {
   // 找到链表的最后
   if (temp.next == null) {//
    break;
   }
   // 如果没有找到最后, 将将temp后移
   temp = temp.next;
  }
  // 当退出while循环时，temp就指向了链表的最后
  // 将最后这个节点的next 指向 新的节点
  temp.next = heroNode;
 }
 // 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
 // (如果有这个排名，则添加失败，并给出提示)
 public void addByOrder(HeroNode heroNode) {
  // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
  // 因为单链表，因为我们找的temp 是位于 添加位置的前一个节点，否则插入不了
  HeroNode temp = head;
  boolean flag = false; // flag标志添加的编号是否存在，默认为false
  while (true) {
   if (temp.next == null) {// 说明temp已经在链表的最后
    break; //
   }
   if (temp.next.no > heroNode.no) { // 位置找到，就在temp的后面插入
    break;
   } else if (temp.next.no == heroNode.no) {// 说明希望添加的heroNode的编号已然存在
    flag = true; // 说明编号存在
    break;
   }
   temp = temp.next; // 后移，遍历当前链表
  }
  // 判断flag 的值
  if (flag) { // 不能添加，说明编号存在
   System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
  } else {
   // 插入到链表中, temp的后面
   heroNode.next = temp.next;
   temp.next = heroNode;
  }
 }
 // 修改节点的信息, 根据no编号来修改，即no编号不能改.
 // 说明
 // 1. 根据 newHeroNode 的 no 来修改即可
 public void update(HeroNode newHeroNode) {
  // 判断是否空
  if (head.next == null) {
   System.out.println("链表为空~");
   return;
  }
  // 找到需要修改的节点, 根据no编号
  // 定义一个辅助变量
  HeroNode temp = head.next;
  boolean flag = false; // 表示是否找到该节点
  while (true) {
   if (temp == null) {
    break; // 已经遍历完链表
   }
   if (temp.no == newHeroNode.no) {
    // 找到
    flag = true;
    break;
   }
   temp = temp.next;
  }
  // 根据flag 判断是否找到要修改的节点
  if (flag) {
   temp.name = newHeroNode.name;
   temp.nickName = newHeroNode.nickName;
  } else { // 没有找到
   System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
  }
 }
 // 删除节点
 // 思路
 // 1. head 不能动，因此我们需要一个temp辅助节点找到待删除节点的前一个节点
 // 2. 说明我们在比较时，是temp.next.no 和 需要删除的节点的no比较
 public void del(int no) {
  HeroNode temp = head;
  boolean flag = false; // 标志是否找到待删除节点的
  while (true) {
   if (temp.next == null) { // 已经到链表的最后
    break;
   }
   if (temp.next.no == no) {
    // 找到的待删除节点的前一个节点temp
    flag = true;
    break;
   }
   temp = temp.next; // temp后移，遍历
  }
  // 判断flag
  if (flag) { // 找到
   // 可以删除
   temp.next = temp.next.next;
  } else {
   System.out.printf("要删除的 %d 节点不存在\n", no);
  }
 }
 // 显示链表[遍历]
 public void list() {
  // 判断链表是否为空
  if (head.next == null) {
   System.out.println("链表为空");
   return;
  }
  // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
  HeroNode temp = head.next;
  while (true) {
   // 判断是否到链表最后
   if (temp == null) {
    break;
   }
   // 输出节点的信息
   System.out.println(temp);
   // 将temp后移， 一定小心
   temp = temp.next;
  }
 }
}
//定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode {
 public int no;
 public String name;
 public String nickName;
 public HeroNode next; // 指向下一个节点
 // 构造器
 public HeroNode(int no, String name, String nickname) {
  this.no = no;
  this.name = name;
  this.nickName = nickname;
 }
 // 为了显示方法，我们重新toString
 @Override
 public String toString() {
  return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
 }
}

4、双向链表

4.1、与单向链表的比较

单向链表，查找的方向只能是一个方向，而双向链表可以向前或者向后查找
单向链表不能自我删除，需要靠辅助节点，而双向链表，则可以自我删除，所以前面我们单链表删除时节点，总是找到 temp ，temp 是待删除节点的前一个节点(认真体会)

4.2、链表节点定义

在单向链表节点的基础上，增加 pre ，用于指向前一个节点

// 定义HeroNode ， 每个HeroNode 对象就是一个节点
class HeroNode {
 public int no;
 public String name;
 public String nickname;
 public HeroNode next; // 指向下一个节点, 默认为null
 public HeroNode pre; // 指向前一个节点, 默认为null
 // 构造器
 public HeroNode(int no, String name, String nickname) {
  this.no = no;
  this.name = name;
  this.nickname = nickname;
 }
 // 为了显示方法，我们重新toString
 @Override
 public String toString() {
  return "HeroNode [no=" + no + ", name=" + name + ", nickname=" + nickname + "]";
 }
}

4.3、链表定义

定义整个链表的头结点，作为链表的入口

// 创建一个双向链表的类
class DoubleLinkedList {
 // 先初始化一个头节点, 头节点不要动, 不存放具体的数据
 private HeroNode head = new HeroNode(0, "", "");
 // 返回头节点
 public HeroNode getHead() {
  return head;
 }
    // ...

4.4、链表遍历

4.4.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点，用于遍历链表
何时停止 while 循环？temp == null：已经遍历至链表尾部

4.4.2、代码实现

// 遍历双向链表的方法
// 显示链表[遍历]
public void list() {
    // 判断链表是否为空
    if (head.next == null) {
        System.out.println("链表为空");
        return;
    }
    // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
    HeroNode temp = head.next;
    while (true) {
        // 判断是否到链表最后
        if (temp == null) {
            break;
        }
        // 输出节点的信息
        System.out.println(temp);
        // 将temp后移， 一定小心
        temp = temp.next;
    }
}

4.5、尾部插入

4.5.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点
何时停止 while 循环？temp.next == null：temp 节点已经是链表最后一个节点，在 temp 节点之后插入 heroNode 节点即可
如何插入？
temp.next 指向新的尾节点 heroNode ：temp.next = heroNode;
heroNode .pre 指向旧的尾节点 temp ：heroNode.pre = temp;

4.5.2、代码实现

在链表尾部插入节点

// 添加一个节点到双向链表的最后.
public void add(HeroNode heroNode) {
    // 因为head节点不能动，因此我们需要一个辅助遍历 temp
    HeroNode temp = head;
    // 遍历链表，找到最后
    while (true) {
        // 找到链表的最后
        if (temp.next == null) {//
            break;
        }
        // 如果没有找到最后, 将将temp后移
        temp = temp.next;
    }
    // 当退出while循环时，temp就指向了链表的最后
    // 形成一个双向链表
    temp.next = heroNode;
    heroNode.pre = temp;
}

4.6、按顺序插入

4.6.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点
我们将 heroNode 节点插入到 temp 节点之后还是 temp 节点之前？

如果插入到 temp 节点之后：

判断条件：temp.next.no > heroNode.no ，即 temp 的下一个节点的值比 heroNode 节点的值大，所以需要将 heroNode 插入到 temp 节点之后

while 循环终止条件：

temp.next == null ：temp 节点已经是链表的尾节点
temp.next.no > heroNode.no：heroNode 节点的值介于 temp 节点的值和 temp 下一个节点的值之间
temp.next.no == heroNode.no：heroNode 节点的值等于 temp 下一个节点的值，不能进行插入

如果插入到 temp 节点之前：

判断条件：temp.no > heroNode.no ，即 temp 节点的值比 heroNode 节点的值大，所以需要将 heroNode 插入到 temp 节点之前

存在的问题：如果需要在链表尾部插入 heroNode 节点，即需要在 null 节点之前插入 heroNode 节点，定位至 null 节点将丢失其前一个节点的信息（除非使用一个变量保存起来），所以跳出循环的判断条件为：temp.next == null

所以我们选取：【插入到 temp 节点之后】方案

4.6.2、代码实现

代码

// 第二种方式在添加英雄时，根据排名将英雄插入到指定位置
// (如果有这个排名，则添加失败，并给出提示)
public void addByOrder(HeroNode heroNode) {
    // 因为头节点不能动，因此我们仍然通过一个辅助指针(变量)来帮助找到添加的位置
    // 目标：在 temp 的后面插入节点
    HeroNode temp = head;
    boolean flag = false; // flag标志添加的编号是否存在，默认为false
    while (true) {
        if (temp.next == null) {// 说明temp已经在链表的最后
            break;
        }
        if (temp.next.no > heroNode.no) { // 位置找到，就在temp的后面插入
            break;
        } else if (temp.next.no == heroNode.no) {// 说明希望添加的heroNode的编号已然存在
            flag = true; // 说明编号存在
            break;
        }
        temp = temp.next; // 后移，遍历当前链表
    }
    // 判断flag 的值
    if (flag) { // 不能添加，说明编号存在
        System.out.printf("准备插入的英雄的编号 %d 已经存在了, 不能加入\n", heroNode.no);
    } else {
        // 插入到链表中, temp的后面
        // heroNode 指向 temp 节点的下一个节点
        heroNode.next = temp.next;
        if(temp.next != null) {
            temp.next.pre = heroNode;
        }
        // temp 节点指向 heroNode 节点
        temp.next = heroNode;
        heroNode.pre = temp;
    }
}

4.7、修改节点信息

4.7.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点
如何找到指定节点？temp.no == no

4.7.2、代码实现

修改指定节点的信息

// 修改一个节点的内容, 可以看到双向链表的节点内容修改和单向链表一样
// 只是 节点类型改成 HeroNode2
public void update(HeroNode newHeroNode) {
    // 判断是否空
    if (head.next == null) {
        System.out.println("链表为空~");
        return;
    }
    // 找到需要修改的节点, 根据no编号
    // 定义一个辅助变量
    HeroNode temp = head.next;
    boolean flag = false; // 表示是否找到该节点
    while (true) {
        if (temp == null) {
            break; // 已经遍历完链表
        }
        if (temp.no == newHeroNode.no) {
            // 找到
            flag = true;
            break;
        }
        temp = temp.next;
    }
    // 根据flag 判断是否找到要修改的节点
    if (flag) {
        temp.name = newHeroNode.name;
        temp.nickname = newHeroNode.nickname;
    } else { // 没有找到
        System.out.printf("没有找到 编号 %d 的节点，不能修改\n", newHeroNode.no);
    }
}

4.8、删除节点

4.8.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点

while 循环的终止条件？由于 temp 节点就是待删除节点，所以终止条件是：temp == null

为何双向链表，可以实现自我删除？定位至待删除的节点 temp ，由于temp 节点有其前一个节点和后一个节点的信息，所以可实现自我删除

如何删除？

temp 的前一个节点的 next 域指向 temp 的后一个节点：temp.pre.next = temp.next;
temp 的后一个节点的 pre 域指向 temp 的前一个节点：temp.next.pre = temp.pre;

有个地方需要注意，如果 temp 已经是链表尾节点，temp 已经没有下一个节点

这时只需要将 temp 的前一个节点的 next 指向 null 即可

所以 temp.next.pre = temp.pre; 执行的前提条件是 temp.next != null

4.8.2、代码实现

删除指定节点

// 从双向链表中删除一个节点,
// 说明
// 1 对于双向链表，我们可以直接找到要删除的这个节点
// 2 找到后，自我删除即可
public void del(int no) {
    // 判断当前链表是否为空
    if (head.next == null) {// 空链表
        System.out.println("链表为空，无法删除");
        return;
    }
    HeroNode temp = head.next; // 辅助变量(指针)
    boolean flag = false; // 标志是否找到待删除节点的
    while (true) {
        if (temp == null) { // 已经到链表的最后
            break;
        }
        if (temp.no == no) {
            // 找到的待删除节点的前一个节点temp
            flag = true;
            break;
        }
        temp = temp.next; // temp后移，遍历
    }
    // 判断flag
    if (flag) { // 找到
        // 可以删除
        // temp.next = temp.next.next;[单向链表]
        temp.pre.next = temp.next;
        // 这里我们的代码有问题?
        // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
        if (temp.next != null) {
            temp.next.pre = temp.pre;
        }
    } else {
        System.out.printf("要删除的 %d 节点不存在\n", no);
    }
}

第 4 章链表（二）

3.2、查找单链表中的倒数第 k 个结点

3.2.1、代码思路

3.2.2、代码实现

3.3、单链表的反转

3.3.1、代码思路

3.3.2、代码实现

3.4、单链表的反转（我的代码）

3.4.1、代码思路

3.4.2、代码实现

3.5、从尾到头打印单链表

3.5.1、栈的基本使用

3.5.2、代码思路

3.5.3、代码实现

3.6、合并两个有序的单链表

3.6.1、代码思路

3.6.2、代码实现

3.7、单向链表所有代码

4、双向链表

4.1、与单向链表的比较

4.2、链表节点定义

4.3、链表定义

4.4、链表遍历

4.4.1、代码思路

4.4.2、代码实现

4.5、尾部插入

4.5.1、代码思路

4.5.2、代码实现

4.6、按顺序插入

4.6.1、代码思路

4.6.2、代码实现

4.7、修改节点信息

4.7.1、代码思路

4.7.2、代码实现

4.8、删除节点

4.8.1、代码思路

4.8.2、代码实现

热门文章

最新文章

相关电子书

第 4 章 链表（二）

3.2、查找单链表中的倒数第 k 个结点

3.2.1、代码思路

3.2.2、代码实现

3.3、单链表的反转

3.3.1、代码思路

3.3.2、代码实现

3.4、单链表的反转（我的代码）

3.4.1、代码思路

3.4.2、代码实现

3.5、从尾到头打印单链表

3.5.1、栈的基本使用

3.5.2、代码思路

3.5.3、代码实现

3.6、合并两个有序的单链表

3.6.1、代码思路

3.6.2、代码实现

3.7、单向链表所有代码

4、双向链表

4.1、与单向链表的比较

4.2、链表节点定义

4.3、链表定义

4.4、链表遍历

4.4.1、代码思路

4.4.2、代码实现

4.5、尾部插入

4.5.1、代码思路

4.5.2、代码实现

4.6、按顺序插入

4.6.1、代码思路

4.6.2、代码实现

4.7、修改节点信息

4.7.1、代码思路

4.7.2、代码实现

4.8、删除节点

4.8.1、代码思路

4.8.2、代码实现

热门文章

最新文章

相关电子书

第 4 章链表（二）