Featured image of post 计算机基础 数据结构与算法 单向链表实现
🏰计算机基础

计算机基础 数据结构与算法 单向链表实现

🌏排序 数据结构与算法实践 🎯 这篇文章用于记录有关 链表数据结构和算法的实现 以及解题的分析和讲解视频

🎄数据结构C实现

🍭头文件大纲

//
// Created by Liu Xianmeng on 2023/10/1 13:47
//
# include <stdio.h>
# include <stdlib.h>

#ifndef CDATASTRCUTRUES_20230930_SINGLELINKEDLIST_H
#define CDATASTRCUTRUES_20230930_SINGLELINKEDLIST_H

// 定义单链表的结点
typedef struct SingleListNode {
    int data;
    struct SingleListNode *next;
}SingleListNode;

// 定义单链表本身
typedef struct SingleList {
    int size;   // 实际大小（存储元素的数目）
    SingleListNode *head; // 单链表的头结点
}SingleList;

/**
 * 初始化单链表
 * @param singleList
 * @return
 */
SingleList* initList(SingleList *singleList) { ... }

/**
 * 向单链表插入元素
 * @param singleList 单链表
 * @param pos        插入元素的位置 下标位置
 * @param e          要插入的元素
 * @return           插入位置不合法 返回-1 插入成功返回1
 */
int insertOne(SingleList *singleList, int pos, int data) { ... }

/**
 * 获取单链表的第pos个元素
 * @param singleList 带dummy哑结点的单链表（第一个head节点不存储数据）
 * @param pos        获取单链表的第pos个元素 -> position位置 非下标位置
 * @param e          接收单链表的第pos个元素
 * @return           成功获取返回1 未获取到返回0
 */
int getElem(SingleList *singleList, int pos, int *e) { ... }

/**
 * 从链表中删除pos位置的元素
 * @param L     带有虚拟头结点的单链表
 * @param pos   pos是元素的序号
 * @param e     接收被删除的值
 * @return 成功删除返回1 删除失败返回0
 */
int deleteOne(SingleList *L, int pos, int *e) { ... }

/**
 * 合并两个有序的链表
 * @param L1
 * @param L2 
 * @return 返回合并的链表L3
 */
SingleList* mergeTwoList(SingleList *L1, SingleList *L2) { ... }

#endif //CDATASTRCUTRUES_20230930_SINGLELINKEDLIST_H

🍭实现初始化函数

/**
 * 初始化单链表 对传入的单链表指针进行初始化并返回
 * @param singleList 传入的单链表指针
 * @return 返回已经初始化的单链表
 */
SingleList* initList(SingleList *singleList) {
    // 申请单链表对象的存储空间
    singleList = (SingleList *) malloc(sizeof(SingleList));
    singleList->size = 0;
    // 申请单链表中头结点的存储空间
    singleList->head = (SingleListNode *)malloc(sizeof(SingleListNode));
    // 分配空间失败返回NULL
    if(!singleList->head) return NULL;
    // 初始化单链表头结点的域
    singleList->head->data = -1;
    singleList->head->next = NULL;
    // 初始化成功返回指针singleList
    return singleList;
}

🍭实现insertOne函数

如果不指定插入的位置 可以编写一个重载的方法默认插入到链表的尾部

/**
 * 向单链表插入单个元素
 * @param singleList 单链表
 * @param pos        插入元素的位置 下标位置
 * @param e          要插入的元素
 * @return           插入位置不合法 返回-1 插入成功返回1
 */
int insertOne(SingleList *singleList, int pos, int data) {
    // 如果插入的位置不合法 返回-1
    if(pos < 0 || pos > singleList->size) {
        return -1;
    }

    /////////// 接下来执行插入操作 关键是找到插入位置的上一个位置 ///////////

    // 1 先用指针p指向头结点
    SingleListNode *p = singleList->head;
    // 2 然后向后移动pos个位置
    for(int i = 1; i <= pos; ++i) p = p->next;
    // 3 执行插入
    // 3.1 先创建一个新的结点并分配空间 初始化数据
    SingleListNode *curNode;
    curNode = (SingleListNode *)malloc(sizeof(SingleListNode));
    curNode->data = data;
    // 3.2 执行插入
    curNode->next = p->next;
    p->next = curNode;
    // 3.3 更新singleList的size大小
    ++singleList->size;

    return 1; // 成功插入数据返回1
}

🍭实现getElem函数

/**
 * 获取单链表的第pos个元素
 * @param singleList 带dummy哑结点的单链表（第一个head节点不存储数据）
 * @param pos        获取单链表的第pos个元素 -> position位置 非下标位置
 * @param e          接收单链表的第pos个元素
 * @return           成功获取返回1 未获取到返回0
 */
int getElem(SingleList *singleList, int pos, int *e) {
    // 链表的元素个数不足pos个 获取不到第pos个元素 返回0
    if(singleList->size < pos) return 0;

    SingleListNode *p; // 声明一个Node指针 用来遍历元素
    p = singleList->head->next; // 从第一个存储数据的结点开始遍历
    int count = 1; // 计数到pos
    while(count != pos) {
        p = p->next;
        ++count;
    }// while循环结束后 p指向目标结点

    // 获取结果
    *e = p->data;
    return 1; // 成功获取到数据返回1
}

⚡阶段测试1

//
// Created by Liu Xianmeng on 2023/10/1 13:47
//
# include <stdio.h>
# include "SingleLinkedList.h"

int main() {
    SingleList *singleList;
    singleList = initList(singleList);
    //////////////// 初始化成功 继续往下走 //////////////
    insertOne(singleList, 0, 10);
    insertOne(singleList, 1, 20);
    insertOne(singleList, 2, 30);

    int num;
    // 依次获取第3、1、2个数据
    getElem(singleList, 3, &num);
    printf("getElem(singleList, 1, &getOneNum) -> 获取到的数字是：%d\n", num);
    getElem(singleList, 1, &num);
    printf("getElem(singleList, 1, &getOneNum) -> 获取到的数字是：%d\n", num);
    getElem(singleList, 2, &num);
    printf("getElem(singleList, 1, &getOneNum) -> 获取到的数字是：%d\n", num);
    return 0;
}

执行结果如下：

🍭实现deleteOne函数

注意删除后需要将被删除的结点的存储空间🎯释放掉

/**
 * 从链表中删除pos位置的元素
 * @param L     带有虚拟头结点的单链表
 * @param pos   pos是元素的序号
 * @param e     接收被删除的值
 * @return 成功删除返回1 删除失败返回0
 */
int deleteOne(SingleList *L, int pos, int *e) {
    // 验证序号不合法 返回0
    if(pos - 1 < 0 || pos - 1 > L->size - 1) return 0;

    // 指针指向虚拟头结点
    SingleListNode *p = L->head;
    // 指针向后移动pos-1个位置
    for(int i = 1; i<= pos - 1; ++i) p = p->next;
    // *e接收被删除的值
    *e = p->next->data;
    // toFreeNode指针暂时指向被删除的结点
    SingleListNode *toFreeNode = p->next;
    // 执行删除操作
    p->next = p->next->next;
    // 🎯释放被删除的结点的存储空间
    free(toFreeNode);

    // 返回结果
    return 1; // 成功删除
}

⚡阶段测试2

//
// Created by Liu Xianmeng on 2023/10/1 13:47
//
# include <stdio.h>
# include "SingleLinkedList.h"

int main() {
    SingleList *singleList;
    singleList = initList(singleList);
    //////////////// 初始化成功 继续往下走 //////////////
    insertOne(singleList, 0, 10);
    insertOne(singleList, 1, 20);
    insertOne(singleList, 2, 30);

    int num;
    deleteOne(singleList, 1, &num);
    printf("deleteOne(singleList, 1, &num) -> 被删除的数字是：%d\n", num);
    getElem(singleList, 1, &num);
    printf("getElem(singleList, 1, &getOneNum) -> 获取到的数字是：%d\n", num);
    return 0;
}

🍭实现mergeTwoList函数

合并两个有序链表 实现的函数中暂不考虑结点的内存释放问题

/**
 * 合并两个有序的链表
 * @param L1
 * @param L2 
 * @return 返回合并的链表L3
 */
SingleList* mergeTwoList(SingleList *L1, SingleList *L2) {
    // 初始化要返回的结果链表
    SingleList *L3 = (SingleList *) malloc(sizeof(SingleList));
    L3->head = (SingleListNode *) malloc(sizeof(SingleListNode));
    L3->head->next = NULL;
    L3->size = L1->size + L2->size; // 直接把L3的size设置为L1和L2的size之和
    
    // 定义三个指针分别来遍历L1、L2、L3
    SingleListNode *p1 = L1->head->next;
    SingleListNode *p2 = L2->head->next;
    SingleListNode *p3 = L3->head;

    SingleListNode *next = NULL;
    while(p1 != NULL && p2 != NULL){
        // 如果当前p1指向的数更小 则合并p1
        if(p1->data <= p2->data) {
            // 暂存p1的next
            next = p1->next;
            // p1的next指向NULL
            p1->next = NULL;
            // p3合并当前的p1结点
            p3->next = p1;
            p3 = p3->next;
            // 更新下一个p1结点
            p1 = next;
        } else { // 否则 合并p2
            // 暂存p1的next
            next = p2->next;
            // p2的next指向NULL
            p2->next = NULL;
            // p3合并当前的p2结点
            p3->next = p2;
            p3 = p3->next;
            // 更新下一个p2结点
            p2 = next;
        }
    }
    // while循环退出后 只能确定有一个链表被合并完了 
    // 需要两个if进行核查是不是还有一个链表没有被合并完 如果没合并完则追加到p3的末尾
    if(p1 != NULL) p3->next = p1;
    if(p2 != NULL) p3->next = p2;

    // 返回合并结果
    return L3;
}

⚡阶段测试3

//
// Created by Liu Xianmeng on 2023/10/1 13:47
//
# include <stdio.h>
# include "SingleLinkedList.h"

int main() {
    // 初始化测试链表1
    SingleList *singleList;
    singleList = initList(singleList);
    insertOne(singleList, 0, 10);
    insertOne(singleList, 1, 20);
    insertOne(singleList, 2, 30);

    // 初始化测试链表2
    SingleList *singleList2;
    singleList2 = initList(singleList2);
    insertOne(singleList2, 0, 16);
    insertOne(singleList2, 1, 26);
    insertOne(singleList2, 2, 36);

    // 执行合并
    SingleList *rst = mergeTwoList(singleList, singleList2);
    printf("断点调试");
    return 0;
}

🎄题目题解

📑牛客 删除有序链表中重复的元素-II （java题解）

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素

给出的链表为1→2→3→3→4→4→5, 返回1→2→5. 给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度 0≤n≤100000≤n≤10000，链表中的值满足 ∣val∣≤1000∣val∣≤1000

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    public static ListNode deleteDuplicates (ListNode head) {}
}

⚡分析

只需要遍历一遍即可求解该题目 需要使用一个标记变量boolean flag标记当前遍历的元素当前节点是不是只出现1次 初始化为true 表示之前没有出现过

每当遍历到一个元素A的时候 首先考虑它是不是原链表的最后一个元素

算法分析如下：

while循环遍历head链表的所有元素{
    if( 1.1当前元素是原链表的最后一个元素){
        if( 1.1.1 当前元素是否已经出现过){
            如果出现过 则直接返回结果✅
        } else 1.1.2 当前元素之前没有出现过{
            则将当前元素加入要返回的链表的尾部
            返回链表✅
        }
    } else 1.2当前元素不是最后一个{
        if(1.2.1 当前元素已经出现过){
            currentNode = nextNode;
        } else 1.2.2 当前元素没有出现过{
            if(1.2.2.1 判断当前元素和下一个元素是否相同){
                相同则currentNode = nextNode;
            } else 1.2.2.2 不同 {
                则将当前元素加入要返回的链表的尾部
                flag = true;
                currentNode = nextNode;
            }
        }
    }
}
返回最终结果✅

具体实现：

import java.util.*;
public class Solution {
    public static ListNode deleteDuplicates (ListNode head) {
        // 要返回的结果链表（哑结点）
        ListNode dummy = new ListNode(-1);
        // 指向要返回的结果链表的尾部
        ListNode rear  = dummy;
        // 当前节点是不是只出现1次 默认只出现1次
        boolean flag = true; 
        // 循环遍历head链表的所有元素
        while(head != null) {
            ListNode next = head.next;
            if(next == null) { 🎯1.1
                if(flag == true) { 🎯1.1.1
                    /******* 拼接一个节点 *******/
                    rear.next = head;
                    rear = head;
                    // 返回结果
                    return dummy.next;
                } else { 🎯1.1.2
                    return dummy.next;
                }
            } else { // next不为null 🎯1.2
                if(next.val == head.val) { // head === next 🎯1.2.1
                    head = next;
                    flag = false; // 当前节点出现不止一次
                } else { // head != next 🎯1.2.2
                    if(flag == false) { 🎯1.2.2.1
                        head = next;
                        flag = true; // 恢复当前只出现1次
                    } else { // flag = true 🎯1.2.2.2
                        /******* 拼接一个节点 *******/
                        head.next = null;
                        rear.next = head;
                        rear = head;
                        head = next;
                    }
                }
            }
        }
        // 返回结果 这个地方被执行的可能只有一种 就是传入的链表本身为空
        // 否则函数一定会在while循环体内返回
        return dummy.next;
    }
}