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

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

逆序