c++反转list样例代码

c++链表反转是一个比较考验基本功的题目。实现方法也有很多种。

本例是使用了递归的方法实现。

思路如下：
假设一个链表有三个元素 A B C

那么反转可以按如下步骤

1. 把尾部B->C改为C->B

   
   第一次尾部变换.PNG

2. 把变换后的尾部A->B改为B->A，完成整个链表反转

   
   第二次尾部变换.PNG

经过两次变换后，整个链表实现了反转。

如果链表节点增加呢，可以同理按照如上步骤操作。只不过是重复尾部反转而已。那么这个操作可以用递归来实现。具体实现代码如下，供参考。

#include <iostream>

using namespace std;

struct node_t {
    int val;
    node_t *next;
};

#define LIST_DEMO_NODE_COUNT 5
struct node_t * create_list_demo() {
    struct node_t *head = nullptr;
    int n = 0;
    while (n++ < LIST_DEMO_NODE_COUNT) {
        struct node_t *node = new struct node_t();
        node->val = n;
        node->next = nullptr;

        if (head == nullptr) {
            head = node;
        } else {
            struct node_t *p = head;
            while (p->next) p = p->next;

            p->next = node;
        }
    }
    return head;
}

void destroy_list_demo(struct node_t * head) {
    struct node_t * p = head;
    struct node_t * q = p;
    while(p) {
        q = p;
        p = p->next;

        delete q;
    }
}

void print_list_demo(struct node_t * head) {
    struct node_t *p = head;
    while (p) {
        cout << p->val << "  ";
        p = p->next;
    }
    cout << endl;
}

void reverse_last_two(struct node_t * tail_prev, struct node_t * tail) {
    tail->next = tail_prev;
    tail_prev->next = nullptr;
}

void find_tail(struct node_t * head, struct node_t * &tail_prev, struct node_t * &tail) {
    tail = head;
    tail_prev = tail;
    while (tail->next) {
        tail_prev = tail;
        tail = tail->next;
    }
}

struct node_t * reverse_list_demo(struct node_t * head) {
    struct node_t * tail_prev = nullptr;
    struct node_t * tail= nullptr;
    find_tail(head, tail_prev, tail);
    struct node_t * reversed_head =tail;

    while(tail != head) {
        reverse_last_two(tail_prev, tail);
        find_tail(head, tail_prev, tail);
    }

    return reversed_head;
}

int main() {
    struct node_t *g_head = nullptr;

    cout << "reverse list demo" << endl;
    g_head = create_list_demo();
    print_list_demo(g_head);

    g_head = reverse_list_demo(g_head);
    print_list_demo(g_head);

    destroy_list_demo(g_head);
    return 0;
}