数据结构 - 反转单链表（C++）_单链表反转c++语言

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击人工智能教程

/*
 * 反转单链表的循环算法（C++）- by Chimomo
 */
 
#include <iostream>
 
#define NULL 0
 
using namespace std;
 
struct Node {
    char data;
    Node *next;
};
 
/**
 * Create single linked list.
 * @return The head pointer.
 */
Node *create() {
    Node *head = NULL;
    Node *rear = head;
    Node *p; // The pointer points to new created node.
    char tmp;
 
    do {
        cout << "Please input positive integer or char '#' to stop: ";
        cin >> tmp;
        if (tmp != '#') {
            p = new Node;
            p->data = tmp;
            p->next = NULL;
 
            if (head == NULL) {
                head = p;
            } else {
                rear->next = p;
            }
            rear = p;
        }
    } while (tmp != '#');
 
    return head;
}
 
/**
 * Print the single linked list.
 * @param head The head pointer.
 */
void print(Node *head) {
    cout << "The current list is: ";
    Node *p = head;
    if (head != NULL) {
        do {
            cout << p->data;
            cout << ' ';
            p = p->next;
        } while (p != NULL);
    }
    cout << "\r\n";
}
 
/**
 * Reverse the single linked list circularly.
 * @param head The head pointer. Use & here since the function body changed the head pointer.
 */
void reverse(Node *&head) {
    if (head == NULL) {
        return;
    }
 
    Node *pre, *cur, *ne;
    pre = head;
    cur = head->next;
    while (cur) {
        ne = cur->next; // Store next pointer.
        cur->next = pre; // Reverse the current code pointer.
        pre = cur;
        cur = ne;
    }
 
    head->next = NULL;
    head = pre;
}
 
int main() {
    Node *list = create();
    print(list);
    reverse(list);
    print(list);
 
    return 0;
}
 
// Output:
/*
Please input positive integer or char '#' to stop:1
 1
Please input positive integer or char '#' to stop:5
 5
Please input positive integer or char '#' to stop:8
 8
Please input positive integer or char '#' to stop:3
 3
Please input positive integer or char '#' to stop:2
 2
Please input positive integer or char '#' to stop:7
 7
Please input positive integer or char '#' to stop:9
 9
Please input positive integer or char '#' to stop:#
 #
The current list is: 1 5 8 3 2 7 9
The current list is: 9 7 2 3 8 5 1
*/

/*
 * 反转单链表的递归算法（C++）- by Chimomo
 */
 
#include <iostream>
 
#define NULL 0
 
using namespace std;
 
struct Node {
    char data;
    Node *next;
};
 
/**
 * Create single linked list.
 * @return The single linked list.
 */
Node *create() {
    Node *head = NULL;
    Node *rear = head;
    Node *p; // The pointer points to the new created node.
    char tmp;
 
    do {
        cout << "Please input positive integer or char '#' to stop: ";
        cin >> tmp;
        if (tmp != '#') {
            p = new Node;
            p->data = tmp;
            p->next = NULL;
 
            if (head == NULL) {
                head = p;
            } else {
                rear->next = p;
            }
            rear = p;
        }
    } while (tmp != '#');
 
    return head;
}
 
/**
 * Print the single linked list.
 * @param head The head pointer.
 */
void print(Node *head) {
    cout << "The current list is: ";
    Node *p = head;
    if (head != NULL) {
        do {
            cout << p->data;
            cout << ' ';
            p = p->next;
        } while (p != NULL);
    }
    cout << "\r\n";
}
 
/**
 * Reverse the single linked list recursively.
 * @param p The pointer.
 * @param head The head pointer. Use & here since the function body changed the head pointer.
 * @return The reversed single linked list head pointer.
 */
Node *reverse(Node *p, Node *&head) {
    if (p == NULL || p->next == NULL) {
        head = p;
        return p;
    }
 
    Node *tmp = reverse(p->next, head);
    tmp->next = p;
    p->next = NULL; // To prevent forming a ring.
    return p;
}
 
int main() {
    Node *list = create();
    print(list);
    reverse(list, list);
    print(list);
 
    return 0;
}
 
// Output:
/*
Please input positive integer or char '#':1
 1
Please input positive integer or char '#':2
 2
Please input positive integer or char '#':4
 4
Please input positive integer or char '#':6
 6
Please input positive integer or char '#':3
 3
Please input positive integer or char '#':8
 8
Please input positive integer or char '#':7
 7
Please input positive integer or char '#':9
 9
Please input positive integer or char '#':0
 0
Please input positive integer or char '#':#
 #
The current list is: 1 2 4 6 3 8 7 9 0
The current list is: 0 9 7 8 3 6 4 2 1
*/