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

2022-03-12 01:00:21

3、链表

3.1 概念介绍

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

链表是以节点的方式来存储数据的，是一种线性的链式存储结构
链表分为带头结点和不带头结点两种
链表的每个节点包含一个data域和一个next域
- data域用来存储数据
- next用来存储下一个节点在内存中的位置
单向带头结点的链表，头结点不存在数据，只有指向第一个元素的地址：

3.2 单向链表实例

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

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

英雄类：

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 + '\'' +
                '}';
    }
}

链表增删改查的思路：

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

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

根据编号进行添加（当需要插入的节点编号存在时，插入失败，并提示），最后使得整个链表的所有节点按编号有序：

思路：首先找到新添加的节点的位置，使得tempNode指针，需要指向带插入位置的前一个；使得newHeroNode.next = tempNode.next,tempNode.next = newHeroNode
修改指定节点的内容，若无指定的节点编号，给出提示

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

删除指定节点：

需要定义临时节点指针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：

首先求取链表的有效元素个数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;
}

思路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;
        }
    }
}

码农公寓

3、链表

3.1 概念介绍

3.2 单向链表实例

3.3 单向链表的常见面试题

3.3.1 求链表有效元素的个数

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

3.3.3 链表的反转

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

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

相关文章