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

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

逆序

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 交换链表当中两个节点题目分析代码

给你一个链表以及两个权值v1和v2,交换链表中权值为v1和v2的这两个节点。保证链表中节点权值各不相同,如果没有找到对应节点,那么什么也不用做。

8220
来自专栏海天一树

小朋友学Python(20):面向对象

一、类与对象 例1 class Employee: 'Base class of employee' empCount = 0 def __i...

33690
来自专栏mukekeheart的iOS之旅

判断两个单链表是否相交(有环、无环两种)

题目描述:   给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。   给定两个链表的头结...

35370
来自专栏Android机器圈

递归 —— 二分查找法 —— 归并排序

二分法就是把一个数组折半查找,再折半直到找到数据位置,或者无数据位置。比如说1-100,你选的值是23,那么范围写法就是(索引写法类似)

20640
来自专栏和蔼的张星的图像处理专栏

451. 两两交换链表中的节点链表处理

给一个链表,两两交换其中的节点,然后返回交换后的链表。 样例 给出 1->2->3->4, 你应该返回的链表是 2->1->4->3。 你的算法只能使用常...

20530
来自专栏书山有路勤为径

k个排序链表的合并

LeetCode 23. Merge k Sorted Lists 已知k个已排序链表头节点指针,将这k个链表合并,合并后仍为有序的,返 回合并后的头节点。

11430
来自专栏程序生活

Leetcode-Easy21. Merge Two Sorted ListsDefinition for singly-linked list.class ListNode:def init(sel

21. Merge Two Sorted Lists 描述: 将两个有序链表进行合并,合并之后的链表也是有序链表 ? 思路: 递归 代码 ...

27930
来自专栏书山有路勤为径

链表中间段逆序

LeetCode 92. Reverse Linked List II 已知链表头节点指针head,将链表从位置m到n逆序。(不申请额外空间)

9220
来自专栏Java技术栈

Java父类强制转换子类原则

最近,微信群友在讨论子类父类的转换问题,其实不难,给大家用实例来说明一下就很明了了。 我们知道Java中子类转换成父类是没有任何问题的,那父类可以转换成子类吗?...

45980
来自专栏武培轩的专栏

剑指Offer-合并两个排序的链表

题目描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 思路 思路一(迭代): 首先处理空链表,当其中一个为空链...

26440

扫码关注云+社区

领取腾讯云代金券