02-数据结构与算法-单向链表

3、链表

3.1 概念介绍

​ 链表是一种有序的线性数据结构,其在内存中的存储不是连续的,存储结构如下:

02-数据结构与算法-单向链表

  • 链表是以节点的方式来存储数据的,是一种线性的链式存储结构

  • 链表分为带头结点和不带头结点两种

  • 链表的每个节点包含一个data域和一个next域

    • data域用来存储数据
    • next用来存储下一个节点在内存中的位置
  • 单向带头结点的链表,头结点不存在数据,只有指向第一个元素的地址:

02-数据结构与算法-单向链表

3.2 单向链表实例

​ 使用带头结点head的单向链表实现:英雄排行榜管理

英雄类包括属性编号(no),姓名(name),绰号(nickName),完成对英雄的增删改查

  1. 英雄类:
package com.kevin.singleListDemo;

/**
 * @author : kevin ding
 * @date : 2022/2/14 22:27
 * @description : 定义一个类来管理英雄节点
 */
public class HeroNode {
    public int no;
    public String name;
    public String nickName;
    public HeroNode next;

    // 构造器
    public HeroNode(){

    }

    public HeroNode(int no, String name, String nickName){
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}

链表增删改查的思路:

  1. 链表的添加操作(假定在链表的尾部添加数据):

定义临时节点tempNode,初始化指向headNode,开始遍历链表,直到遍历到链表的末尾,将新的节点添加到末尾:tempNode.next=newHeroNode

  1. 根据编号进行添加(当需要插入的节点编号存在时,插入失败,并提示),最后使得整个链表的所有节点按编号有序:

    思路:首先找到新添加的节点的位置,使得tempNode指针,需要指向带插入位置的前一个;使得newHeroNode.next = tempNode.next,tempNode.next = newHeroNode

  2. 修改指定节点的内容,若无指定的节点编号,给出提示

首先tempNode节点指针找到指定的节点,随后,将该节点的属性值进行修改

  1. 删除指定节点:

需要定义临时节点指针tempNode指向找待删除节点的前一个节点,tempNode.next= tempNode.next.next

单向链表整体增删改查功能的代码:

package com.kevin.singleListDemo;
/**
 * @author : kevin ding
 * @date : 2022/2/14 22:04
 * @description : 单链表的类
 */
public class SingleLinkedList {
    // 首先给链表初始化一个头结点
    private HeroNode headNode = new HeroNode();

    // 方法 addNode 添加节点:(默认往队尾添加)
    // 对于给定的节点,找到链表的队尾,将给定的节点插入
    public void addNode(HeroNode heroNode){
        // 因为头结点headNode不能移动,需要一个辅助节点(默认初始指向头结点)进行移动,找到最后一个节点
        HeroNode tempNode = headNode;
        // 开始遍历链表找到链表的最后一个节点
        while (true){
            if(tempNode.next == null){
                break;
            }
            tempNode = tempNode.next;
        }
        // 退出循环时,tempNode指向最后一个节点.让其next指向新加的heroNode即可
        tempNode.next = heroNode;
    }

    // 方法 按照节点编号进行添加,当该节点存在时,提示添加失败
    public void addNodeByOrder(HeroNode heroNode){
        // 因为头结点不能动,所以需要定义临时节点变量,来移动
        HeroNode tempNode = headNode;
        // 定义一个标记变量,来判断当前节点的no是否存在于链表中,默认false。如果存在则添加失败
        boolean flag = false;
        // 开始进行遍历
        while (true){
            // 如果遍历到最后,则直接返回
            if(tempNode.next == null){
                break;
            }
            // 如果当前节点的下一个节点的no值大于待插入的节点,则找到了正确的位置
            if(tempNode.next.no > heroNode.no){
                break;
            }else if(tempNode.next.no == heroNode.no){
                // 如果相等,表示当前节点编号已经存在于链表中,将标记位置为true
                flag = true;
                break;
            }
            tempNode = tempNode.next;
        }
        // 循环结束,此时temp节点的下一个即为带插入的位置
        // 当flag为true时不能插入
        if(flag){
            System.out.println("当前节点"+ tempNode.no+ "已经存在,不能重复添加......");
        }else {
            // 插入到tempNode的后面即可
            heroNode.next = tempNode.next;
            tempNode.next = heroNode;
        }
    }


    // 遍历链表的所有节点:
    public void showAllNodes(){
        // 首先判断链表是否为空,如果为空直接返回
        if(headNode.next == null){
            System.out.println("链表为空......");
            return;
        }
        // 头结点不能动,需要指定一个辅助节点,因为已经判断过head。next不为空,则初始指向头结点的next,即第一个元素
        HeroNode tempNode = headNode.next;
        // 循环遍历所有节点,并显示即可
        while (true){
            // 每次针对当前节点判断其是否为空即可
            if(tempNode == null){
                break;
            }
            // 当前节点不为空,将其打印出来,并将指针后移
            System.out.println("当前节点的英雄为:" + tempNode);
            tempNode = tempNode.next;
        }
    }


    // 修改列表中指定节点的值
    public void  updateNode(HeroNode heroNode){
        // 首先判断链表是否为空
        if(headNode.next == null){
            System.out.println("链表为空......");
            return;
        }
        // 定义一个临时节点,指向第一个节点元素
        HeroNode tempNode = headNode.next;
        // 遍历找到节点
        boolean flag = false;
        while (true){
            if(tempNode == null){
                break;
            }
            if(tempNode.no == heroNode.no){
                flag = true;
                break;
            }
            // 千万不能忘记将节点后移
            tempNode = tempNode.next;
        }
        if(flag){
            // 表示找到了该节点,进行更新操作
            tempNode.name = heroNode.name;
            tempNode.nickName = heroNode.nickName;
        }else {
            // 链表中没有指定的节点
            System.out.println("链表中没有指定的节点:" + heroNode.no);

        }
    }

    // 删除指定编号的节点
    public void deleteNode(int no){
        // 首先判断节点是否为空
        if(headNode.next == null){
            System.out.println("链表为空......");
            return;
        }
        // 头结点不能动,需要定义临时节点,找到待删除节点的前一个节点
        HeroNode tempNode = headNode;
        boolean flag = false;
        while(true){
            if(tempNode.next == null){
                // 遍历到了链表我的最后一个位置
                break;
            }
            if(tempNode.next.no == no){
                // 找到了待删除的节点
                flag = true;
                break;
            }

            tempNode = tempNode.next;
        }

        // 退出循环后,判断是否找到
        if(flag){
            //进行删除操作
            tempNode.next = tempNode.next.next;
        }else {
            // 没有找到待删除的节点
            System.out.println("没有找到待删除的节点:" + no);
        }
    }



}

测试验证:

package com.kevin.singleListDemo;

/**
 * @author : kevin ding
 * @date : 2022/2/14 22:24
 * @description : 单向链表的测试类
 */
public class SingleLinkedListTestDemo {
    public static void main(String[] args) {
        // 首先创建一些节点:
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");
        HeroNode heroNode4 = new HeroNode(4, "林冲", "豹子头");
        HeroNode heroNode5 = new HeroNode(5, "鲁智深", "花和尚");
        HeroNode heroNode6 = new HeroNode(4, "鲁智深2", "花和尚2");

        // 创建一个空的单链表
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addNodeByOrder(heroNode1);
        singleLinkedList.addNodeByOrder(heroNode5);
        singleLinkedList.addNodeByOrder(heroNode2);
        singleLinkedList.addNodeByOrder(heroNode4);
        singleLinkedList.addNodeByOrder(heroNode3);

        // 显示列表
        singleLinkedList.showAllNodes();

        singleLinkedList.addNodeByOrder(heroNode6);


        // 修改链表
        singleLinkedList.updateNode(new HeroNode(3, "吴用~", "智多星..." ));

        // 修改后链表的显示
        System.out.println("修改后链表的显示。。。。。。。。");
        singleLinkedList.showAllNodes();

        singleLinkedList.updateNode(new HeroNode(7, "...", "===="));

        // 删除指定的链表
        singleLinkedList.deleteNode(4);
        System.out.println("删除节点之后遍历================");
        singleLinkedList.showAllNodes();

        System.out.println("删除节点之后遍历================");
        singleLinkedList.deleteNode(5);
        singleLinkedList.showAllNodes();

        System.out.println("删除节点之后遍历================");
        singleLinkedList.deleteNode(1);
        singleLinkedList.showAllNodes();


    }
}

3.3 单向链表的常见面试题

3.3.1 求链表有效元素的个数

思路:给定链表,当链表为空时,直接返回0;否则指定一个临时节点tempNode指针(初始化为第一个节点),和一个计数变量(初始化为0),若当前节点不为空,则技术变量+1,节点指向后移一位;

代码实现:

// 获取链表有效元素的个数
public int getValidNums(){
    // 当链表为空的时候,直接返回0
    if (headNode.next == null){
        System.out.println("链表为空....");
        return 0;
    }
    // 当链表不为空的时候,因为链表的头部不能动,指定一个临时节点变量,进行元素的遍历,
    // 定义计数变量
    int count = 0;
    HeroNode tempNode = headNode.next;
    while(tempNode != null){
        // 当前节点不为空,则count加1,tempNode后移
        count += 1;
        tempNode = tempNode.next;
    }

    // 当循环退出时,表明当前指向节点为null,遍历结束
    return count;
}

3.3.2 查找链表中的倒数第k个节点

  1. 思路1:
  • 首先求取链表的有效元素个数n,和k进行比较进行参数校验(0<k<=n)
  • 定义tempNode节点指向头结点后的第一个节点,使得tempNode向后移动n-k次,
  • 此时tempNode指向的节点即为倒数第k个节点

代码实现:

//获取倒数第k个节点
public HeroNode getLastKthNode(int k){
    // 如果链表为空;
    if (headNode.next == null){
        System.out.println("链表为空...");
        return null;
    }
    // 获取链表的有效元素个数
    int size = getValidNums();
    // 对输入参数进行校验:
    if( k <= 0 || k > size){
        System.out.println("输入参数k值有误...");
        return null;
    }
    // 临时节点,初始化指向第一个元素
    HeroNode tempNode = headNode.next;
    // 遍历size-k次,
    for (int i = 0; i < size - k; i++) {
        tempNode = tempNode.next;
    }
    // 当循环结束时,tempNode指向的即为倒数第k个节点
    return tempNode;
}
  1. 思路2:
  • 首先对k值进行校验,判断链表是否为空
  • 定义两个指针节点,初始化指向第一个节点,先让right节点走k-1步,若在此期间到达了末尾,则链表长度小于k
  • 走了k-1步之后,left指针和right同时移动,当right指向最后一个节点时,此时left指向了倒数第k个节点

代码实现:

// 获取倒数第k个节点的第二种解法
public HeroNode getLastKthNode2(int k){
    // 首先判空
    if (headNode.next == null){
        System.out.println("链表为空...");
        return null;
    }
    // 验证k的有效性
    if (k <= 0){
        System.out.println("输入参数k值有误...");
        return null;
    }
    // 定义两个临时节点leftNode 和rightNode 初始化均指向第一个节点位置
    // 让rightNode先走k-1步,(在此期间如果rightNode已经指向末尾,直接返回null,说明链表长度不够)
    HeroNode leftNode = headNode.next;
    HeroNode rightNode = headNode.next;

    for (int i = 0; i < k-1 ; i++) {
        if(rightNode.next == null){
            System.out.println( k + "大于了链表的长度,无效...");
            return null;
        }
        rightNode = rightNode.next;
    }
    // 随后 两个指针同时移动,当rightNode移动到末尾时,leftNode即为倒数第k个
    while (true){
        if(rightNode.next == null){
            // 当rightNode.next指向null时,说明此时rightNode已经位于最后一个
            break;
        }else {
            //否则 需要将left和right同时后移
            leftNode = leftNode.next;
            rightNode = rightNode.next;
        }
    }
    // 当循环退出之后,此时left已经指向倒数第k个
    return leftNode;
}

3.3.3 链表的反转

思路:

  • 首先如果链表为空或者只有一个节点,则无需翻转
  • 定义新的头结点,临时变量指向原链表的头结点,对原链表进行遍历,每次遍历到的值,插入到新链表的第一个节点位置;
  • 由于原链表的当前节点插入到新链表,又不能是原链表丢失,因此需要再定义一个节点指向原链表中当前节点的下一个
  • 遍历完成,全部添加到新的链表中之后,使得原链表头结点的下一个指向当前新链表的第一个节点。

代码实现:

// 链表的翻转
public void reverseLinkedList(){
    // 边界条件判断
    if(headNode.next == null || headNode.next.next == null){
        return;
    }
    // 定义新的链表头结点,临时节点、临时节点的下一个节点
    HeroNode reversedHeadNode = new HeroNode(0,"","");
    HeroNode tempNode = headNode.next;
    HeroNode nextNode = null;
    // 遍历原链表,当前节点若不为空,就将其加入到新链表头结点的第一个元素位置
    while(tempNode != null){
        // 首先需要给nextNode赋值,指向tempNode的下一个节点
        nextNode = tempNode.next;
        // 将tempNode插入到新链表头结点的第一个元素位置(插入元素的操作)
        tempNode.next = reversedHeadNode.next;
        reversedHeadNode.next = tempNode;
        // 将tempNode后移一位,直接等于nextNode即可
        tempNode = nextNode;

    }
    // 循环退出,则表示翻转完毕,将原链表的头结点的next指向新链表头结点的next
    headNode.next = reversedHeadNode.next;
}

3.3.4 从尾到头打印单链表的元素

思路1:使用翻转链表:先翻转,遍历打印,再反转回原来的样子

代码实现:

public void reversePrintAllNodes1(){
    // 通过翻转链表实现
    if(headNode.next == null){
        System.out.println("链表为空...");
        return;
    }
    // 翻转链表
    reverseLinkedList();
    // 遍历所有节点
    showAllNodes();
    // 再将链表翻转回原样
    reverseLinkedList();
}

思路2:使用栈先进后出的特性

  • 定义栈的数据结构,存储HeroNode类型数据

  • 定义临时节点指向第一个元素,开始遍历链表,每次将元素存储到栈中

  • 链表遍历完之后,将栈中所有的元素依次弹出,即可实现反向遍历

代码实现:

public void reversePrintAllNodes(){
    // 首先判断栈是否为空
    if(headNode.next == null){
        System.out.println("栈为空");
    }
    // 定义栈的数据结构,来存储每次遍历到的数据,利用栈先进后出的特点,实现反向遍历
    Stack<HeroNode> heroNodeStack = new Stack<>();
    HeroNode tempNode = headNode.next;
    while(tempNode != null){
        heroNodeStack.push(tempNode);
        tempNode = tempNode.next;
    }
    // 循环退出时,临时节点指针指向了末尾,随后开始将stack中的元素出栈,完成反向遍历
    while(heroNodeStack.size() > 0){
        HeroNode heroNode = heroNodeStack.pop();
        System.out.println(heroNode);
    }

}

3.3.5 将两个有序的链表成一个有序链表

思路分析:

  • 首先判断给定的两个链表是否为空,若链表1为空,则将链表2即为结果;若链表2为空则链表1为结果
  • 定义2个临时节点,分别指向链表1和链表2的第一个元素,在定义临时节点指向新链表的头结点
  • 循环遍历开始进行链表1和2元素值的比较,将较小的值追加到新链表的末尾,直到其中一个链表遍历结束
  • 最后将还没有遍历结束的链表所有节点追加到新链表的后面

代码实现:

package com.kevin.singleListDemo;

/**
 * @author : kevin ding
 * @date : 2022/2/24 20:42
 * @description :
 */
public class CombinedTwoOrderLinkedList {

    public HeroNode mergeTwoOrderLinkedListToOne(HeroNode headNode1, HeroNode headNode2){
        // 需要定义一个新的链表的头结点
        HeroNode newHeadNode = new HeroNode(0, "","");
        // 首先判断两个链表是否为空:
        if(headNode1.next == null){
            newHeadNode.next = headNode2.next;
            return newHeadNode;
        }
        if(headNode2.next == null){
            newHeadNode.next = headNode1.next;
            return newHeadNode;
        }

        // 如果两个链表都不为空,需要定义三个临时变量 ,分别指向三个头结点的下一个位置
        HeroNode tempNode1 = headNode1.next;
        HeroNode tempNode2 = headNode2.next;
        HeroNode newTempNode = newHeadNode;
        HeroNode nextNode1 = null;
        HeroNode nextNode2 = null;
        // 开始进行比较当前哪个节点我的值大,直到其中一个链表遍历到最后
        while (tempNode1 != null && tempNode2 != null){

            if(tempNode1.no <= tempNode2.no){
                nextNode1 = tempNode1.next;
                //将tempNode1的节点放到newTemNode的后面
                newTempNode.next = tempNode1;
                tempNode1 = nextNode1;
                // 随后将newTempNode后移
                newTempNode = newTempNode.next;

            }else{
                nextNode2 = tempNode2.next;
                //将tempNode2的节点放到newTemNode的后面
                newTempNode.next = tempNode2;
                tempNode2 = nextNode2;
                // 随后将newTempNode后移
                newTempNode = newTempNode.next;
            }
        }
        // 循环退出表示其中一个已经为空
        if(tempNode1 == null){
            // tempNode2后面所有的元素追加到newTempNode后面
            newTempNode.next = tempNode2;
        }
        if(tempNode2 == null){
            // 将tempNode1后面的所有元素追加到newTempNode后面
            newTempNode.next = tempNode1;
        }

        return newHeadNode;
    }

    // 给定一个头结点,开始遍历其中的所有元素
    public void printAllNodesByHeadNode(HeroNode node){
        if(node.next == null){
            System.out.println("链表为空......");
            return;
        }

        // 头结点不能动,需要指定一个辅助节点,因为已经判断过head。next不为空,则初始指向头结点的next,即第一个元素
        HeroNode tempNode = node.next;
        // 循环遍历所有节点,并显示即可
        while (true){
            // 每次针对当前节点判断其是否为空即可
            if(tempNode == null){
                break;
            }
            // 当前节点不为空,将其打印出来,并将指针后移
            System.out.println("当前节点的英雄为:" + tempNode);
            tempNode = tempNode.next;
        }
    }
}
上一篇:LSF0108 level shift设计使用及debug流程


下一篇:Pandas:从CSV中读取一个含有datetime类型的DataFrame