单项链表逆序

分手后的思念是犯贱 2022-06-06 12:25 165阅读 0赞

程序1：

//
    //  main.cpp
    //  testC++06ReverseSingleLinkedList
    //
    //  Created by fei dou on 12-8-9.
    //  Copyright (c) 2012年 vrlab. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    
    typedef struct node{
        char data;
        node * next;
    }Node;
    
    /*从头插入链表*/
    inline void insertIntoListFromHead(char data, Node* (&head))
    {
        Node *newNode = new Node();
        newNode -> data = data;
        newNode -> next = head;
        head = newNode;
    }
    
    /*翻转链表*/
    Node * reverseSingleLinkedList(Node *head);
    void printList(Node *head);
    
    void printList(Node *head)
    {
        while(head)
        {
            cout << head -> data << "   ";
            head = head -> next;
        }
    }
    
    
    /*完成单项链表的逆序操作*/
    Node * reverseSingleLinkedList(Node *head)
    {
        Node *newHead = NULL;
        while (head)
        {
            Node *headNext = head -> next;          //保存head下一个节点
            head -> next = newHead;                 //从头插入新的反向链表中
            newHead = head;                         //从头插入新的反向链表中
            head = headNext;                        //head重新指向还没有反向的链表的头部
        }
        return newHead;
    }
    
    
    int main (int argc, const char * argv[])
    {
    
        Node *listHead = NULL;
        for (char ch = 'f'; ch >= 'a'; --ch)
            insertIntoListFromHead(ch, listHead);
        cout << "原始列表内容是：" <<endl;
        printList(listHead);
        listHead = reverseSingleLinkedList(listHead);
        cout << endl << "逆序后的结果是：" << endl;
        printList(listHead);
        cout << endl;
        /*释放空间*/
        while (listHead)
        {
            Node *delNode = listHead;
            listHead = listHead -> next;
            delete  delNode;
            delNode = NULL;
        }
        return 0;
    }

程序2：

//
    //  main.cpp
    //  testC++06ReverseSingleLinkedList
    //
    //  Created by fei dou on 12-8-9.
    //  Copyright (c) 2012年 vrlab. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    
    typedef struct node{
        char data;
        node * next;
    }Node;
    
    /*从头插入链表*/
    inline void insertIntoListFromHead(char data, Node* (&head))
    {
        Node *newNode = new Node();
        newNode -> data = data;
        newNode -> next = head;
        head = newNode;
    }
    
    /*从头插入链表*/
    inline void insertIntoListFromHead(Node *insertNode, Node* (&head))
    {
        if (!insertNode) return;
        insertNode -> next = head;
        head = insertNode;
    }
    
    /*翻转链表*/
    Node * reverseSingleLinkedList(Node *head);
    void printList(Node *head);
    
    void printList(Node *head)
    {
        while(head)
        {
            cout << head -> data << "   ";
            head = head -> next;
        }
    }
    
    
    /*完成单项链表的逆序操作*/
    Node * reverseSingleLinkedList(Node *head)
    {
        Node *newHead = NULL;
        while (head)
        {
            Node *headNext = head -> next;          //保存head下一个节点
            insertIntoListFromHead(head, newHead);  //从头插入到逆序链表中
            head = headNext;                        //head重新指向还没有反向的链表的头部
        }
        return newHead;
    }
    
    
    int main (int argc, const char * argv[])
    {
        
        Node *listHead = NULL;
        for (char ch = 'f'; ch >= 'a'; --ch)
            insertIntoListFromHead(ch, listHead);
        cout << "原始列表内容是：" <<endl;
        printList(listHead);
        listHead = reverseSingleLinkedList(listHead);
        cout << endl << "逆序后的结果是：" << endl;
        printList(listHead);
        cout << endl;
        /*释放空间*/
        while (listHead)
        {
            Node *delNode = listHead;
            listHead = listHead -> next;
            delete  delNode;
            delNode = NULL;
        }
        return 0;
    }

程序3：

//
    //  main.cpp
    //  testC++06ReverseSingleLinkedList
    //
    //  Created by fei dou on 12-8-9.
    //  Copyright (c) 2012年 vrlab. All rights reserved.
    //
    
    #include <iostream>
    using namespace std;
    
    typedef struct node{
        char data;
        node * next;
    }Node;
    
    /*从头插入链表*/
    inline void insertIntoListFromHead(char data, Node* (&head))
    {
        Node *newNode = new Node();
        newNode -> data = data;
        newNode -> next = head;
        head = newNode;
    }
    
    /*从头插入链表*/
    inline void insertIntoListFromHead(Node *insertNode, Node* (&head))
    {
        if (!insertNode) return;
        insertNode -> next = head;
        head = insertNode;
    }
    
    /*翻转链表*/
    Node * reverseSingleLinkedList(Node *head);
    void printList(Node *head);
    
    void printList(Node *head)
    {
        while(head)
        {
            cout << head -> data << "   ";
            head = head -> next;
        }
    }
    
    
    /*完成单项链表的逆序操作*/
    Node * reverseSingleLinkedList(Node *head)
    {
        if (head == NULL || head -> next == NULL) return  head;
        Node * subReversedList = reverseSingleLinkedList(head -> next);
        head -> next -> next = head;
        head -> next = NULL;
        return subReversedList;
    }
    
    
    
    int main (int argc, const char * argv[])
    {
        
        Node *listHead = NULL;
        for (char ch = 'f'; ch >= 'a'; --ch)
            insertIntoListFromHead(ch, listHead);
        cout << "原始列表内容是：" <<endl;
        printList(listHead);
        listHead = reverseSingleLinkedList(listHead);
        cout << endl << "逆序后的结果是：" << endl;
        printList(listHead);
        cout << endl;
        /*释放空间*/
        while (listHead)
        {
            Node *delNode = listHead;
            listHead = listHead -> next;
            delete  delNode;
            delNode = NULL;
        }
        return 0;
    }

上面三个程序相信都能读懂，这里不在进行解释