<算法>图解逆序单向链表全过程

简介: 4个桶, 桶上都分别标着特定的标签1, 2, 3, 4; 桶里有对应的4个球,标着和桶一样的编号;问题来了, 让所有桶和桶内球的编号之和都为5, 在交换的过程中,不能增加额外的桶, 且球不能着地,应该如何解决呢,最好的方式就是多找几个人,手持球完成...

4个桶, 桶上都分别标着特定的标签1, 2, 3, 4; 桶里有对应的4个球,标着和桶一样的编号;
问题来了, 让所有桶和桶内球的编号之和都为5, 在交换的过程中,不能增加额外的桶, 且球不能着地,应该如何解决呢,最好的方式就是多找几个人,手持球完成交换;

事实上, 在单向链表逆序的过程中: 我们也需要使用指针来代替人的作用

链表由多个结点组成, 每一个结点可被看做最小的单位.
要求在不开辟新内存空间的情况下,完成链表的逆序

0
1
2
3
4
5

6
7

8
# include <stdio.h>

// 定义链表结点
struct ListNode{
    // 定义结点的值
    int n_val;
    // 定义结点指向下一个结点的指针的值
    ListNode* p_next;
    // 结构体默认构造方法
    ListNode(int x): n_val(x), p_next(NULL) {};
};

// 定义逆序类
class Solution{
public:
    // 传入链表头部结点的指针(直接用指针修改原数组 的排列情况)
    ListNode* reverseList(ListNode* head){
        // 创建一个新的ListNode类型的指针, 用于最后的返回值(开辟第一个指针空间)
        ListNode *new_head = NULL;
        // 开始遍历整个链表, 重排为新的链表
        while(head){
            // 创建临时结点, 存储 当前head结点 的指向(开辟第二个指针空间)
            ListNode* tmp = head->p_next;
            // 将当前结点指向到 new_head
            head->p_next = new_head;
            // 将new_head指向head当前的结点
            new_head = head;
            // 将head结点后移一个单位;
            head = tmp;
        }
        return new_head;
    }
};

int main(){

    // 初始化值
    ListNode a(10);
    ListNode b(20);
    ListNode c(30);
    ListNode d(40);

    a.p_next = &b;
    b.p_next = &c;
    c.p_next = &d;
    d.p_next = NULL;

    // 实例化方法
    Solution solve;
    // 获取链表头指针
    ListNode *head = &a;

    printf("转置之前的链表为:\n");
    while (head){
        // 打印当前指针所在结点的值
        printf("%d\n", head->n_val);
        // 指针后移
        head = head->p_next;
    }
    // 执行转置
    head = solve.reverseList(&a);
    printf("转置之后的链表为:\n");

    
    while (head) {
        printf("%d\n", head->n_val);
        head = head->p_next;
    }
    return 0;
}
逆序
目录
相关文章
|
2月前
【数据结构】单链表之--无头单向非循环链表
【数据结构】单链表之--无头单向非循环链表
|
2月前
|
算法 测试技术 C++
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组
|
2月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-7 算法训练 逆序对 平衡二叉树
40 0
|
2月前
|
存储 JavaScript 算法
TypeScript算法专题 - blog4 - 单链表节点的两-两翻转(两两一组逆序)
TypeScript算法专题 - blog4 - 单链表节点的两-两翻转(两两一组逆序)
36 0
|
2月前
|
存储
数据结构第二课 -----线性表之单向链表
数据结构第二课 -----线性表之单向链表
|
1月前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
1月前
|
算法 C语言
数据结构——单向链表(C语言版)
数据结构——单向链表(C语言版)
24 2
|
24天前
|
Java
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
8 0
|
25天前
|
存储 算法 前端开发
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
13 0