[数据结构与算法] 尚硅谷算法与数据结构学习笔记02 -- 单链表

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 尚硅谷算法与数据结构学习笔记02 -- 单链表 -> 正文阅读

[数据结构与算法]尚硅谷算法与数据结构学习笔记02 -- 单链表

1、链表(Linked List)介绍

1.1、内存结构

内存上来看：链表存储空间不连续（不像数组）

1.2、逻辑结构

逻辑上来看：链表属于线性结构

1.3、链表特点

链表是以节点的方式来存储，是链式存储
data 域存放数据，next 域指向下一个节点
链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

2、链表应用场景

2.1、水浒英雄榜

使用带 head 头的单向链表实现【水浒英雄排行榜管理】

2.2、链表节点定义

no ：英雄编号
name ：英雄名字
nickName ：英雄昵称
next ：指向下一个 HeroNode 节点

//定义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 + "]";
	}
}

2.3、链表定义

DummyHead ：头结点不存放数据，仅仅作为当前链表的入口
head 字段的值不能改变，一旦改变，就丢失了整个链表的入口，我们也就无法通过 head 找到链表了

//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList {
	// 先初始化一个头节点, 头节点不要动, 不存放具体的数据
	private HeroNode head = new HeroNode(0, "", "");

	// 返回头节点
	public HeroNode getHead() {
		return head;
	}
    
    // ....

2.4、遍历链表

2.4.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点
何时遍历完成？temp == null 表明当前节点为 null ，即表示已到链表末尾
如何遍历？temp = temp.next ，每次输出当前节点信息之后，temp 指针后移

2.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;
	}
}

2.5、尾部插入

2.5.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点
如何在链表末尾插入节点？
- 首先需要遍历链表，找到链表最后一个节点，当 temp.next == null时，temp 节点指向链表最后一个节点
- 然后在 temp 节点之后插入节点即可：temp.next = heroNode

2.5.2、代码实现

在链表尾部插入节点

// 添加节点到单向链表
// 思路，当不考虑编号顺序时
// 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 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();
}

程序运行结果

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

2.6、按顺序插入

2.6.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点
应该如何执行插入？（待插入节点为 heroNode）
- 首先需要遍历链表，找到链表中编号值比 heroNode.no 大的节点，暂且叫它 biggerNode ，然后把 heroNode 插入到 biggerNode 之前即可
- 怎么找 biggerNode ？当 temp.next.no > heroNode.no 时，这时 temp.next 节点就是 biggerNode 节点。
- 为什么是 temp.next 节点？只有找到 temp 节点和 temp.next（biggerNode ）节点，才能在 temp 节点和 temp.next 节点之间插入 heroNode 节点
- 怎么插入？
  - heroNode .next = temp.next;
  - temp.next = heroNode;

2.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.next = temp.next;
        temp.next = heroNode;
    }
}

测试代码

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.addByOrder(hero1);
    singleLinkedList.addByOrder(hero4);
    singleLinkedList.addByOrder(hero2);
    singleLinkedList.addByOrder(hero3);

    // 显示数据
    singleLinkedList.list();
}

程序运行结果

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

2.7、修改节点信息

2.7.1、代码思路

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

2.7.2、代码实现

修改指定节点信息

// 修改节点的信息, 根据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);
   }
}

测试代码

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.addByOrder(hero1);
    singleLinkedList.addByOrder(hero4);
    singleLinkedList.addByOrder(hero2);
    singleLinkedList.addByOrder(hero3);

    // 测试修改节点的代码
    HeroNode newHeroNode = new HeroNode(2, "小卢", "玉麒麟~~");
    singleLinkedList.update(newHeroNode);

    singleLinkedList.list();
}

程序运行结果

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

2.8、删除节点

2.8.1、代码思路

定义辅助变量 temp ，相当于一个指针，指向当前节点
如何找到待删除的节点？遍历链表，当 temp.next == no 时，temp.next 节点就是待删除的节点
如何删除？temp = temp.next.next 即可删除 temp.next 节点，该节点没有引用指向它，会被垃圾回收机制回收

2.8.2、代码实现

删除指定节点

// 删除节点
// 思路
// 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 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.del(1);
    singleLinkedList.del(4);

    singleLinkedList.list();
}

程序运行结果

HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]

2.9、总结

遍历链表，执行操作时，判断条件有时候是 temp ，有时候是 temp.next ，Why？
- 对于插入、删除节点来说，需要知道当前待操作的节点（heroNode）前一个节点的地址（指针），如果直接定位至当前待操作的节点 heroNode ，那没得玩。。。因为不知道heroNode 前一个节点的地址，无法进行插入、删除操作，所以 while 循环中的条件使用 temp.next 进行判断
- 对于更新、遍历操作来说，我需要的仅仅就只是当前节点的信息，所以 while 循环中的条件使用 temp进行判断
头结点与首节点
- 参考资料：https://blog.csdn.net/WYpersist/article/details/80288056
- 头结点是为了操作的统一与方便而设立的，放在第一个元素结点之前，其数据域一般无意义（当然有些情况下也可存放链表的长度、用做监视哨等等）。
- 首元结点也就是第一个元素的结点，它是头结点后边的第一个结点。

3、单链表面试题

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

3.1.1、代码思路

求单链表中有效节点的个数：遍历即可

3.1.2、代码实现

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

// 方法：获取到单链表的节点的个数(如果是带头结点的链表，需求不统计头节点)
/**
 * 
 * @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;
}

测试代码

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();

    // 测试一下 求单链表中有效节点的个数
    System.out.println("有效的节点个数=" + getLength(singleLinkedList.getHead()));
}

程序运行结果

HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
有效的节点个数=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 ：已遍历至链表尾部

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 + "]";
 	}
 
 }

数据结构与算法最新文章

【力扣106】从中序与后续遍历序列构造二叉

leetcode 322 零钱兑换

哈希的应用：海量数据处理

动态规划|最短Hamilton路径

华为机试_HJ41 称砝码【中等】【menset】【

【C与数据结构】——寒假提高每日练习Day1

基础算法——堆排序

2023王道数据结构线性表--单链表课后习题部

LeetCode 之反转链表的一部分

【题解】lintcode必刷50题＜有效的括号序列

加:2021-10-19 12:08:35 更:2021-10-19 12:09:37

360图书馆购物三丰科技阅读网日历万年历 2024年11日历

-2024/11/26 7:20:32-

图片自动播放器
↓图片自动播放器↓

TxT小说阅读器
↓语音阅读,小说下载,古典文学↓

一键清除垃圾
↓轻轻一点,清除系统垃圾↓

图片批量下载器
↓批量下载图片,美女图库↓

网站联系: qq:121756557 email:121756557@qq.com IT数码