シングルチェーンテーブルの反転を実現

単一チェーンテーブルの反転を実現する主な考え方:

の3つのノードは、開始時に中間ノードがヘッダノードを指し、第1のノードがNULLを指し、第3のノードがヘッダノードの次のノードを指す.

中間ノードを

に反転する.

の3つのノードはいずれも1格

を後方に移動する.

終了条件

であるか否かを判断する.
チェーンテーブルの使用が終了すると、メモリを解放する必要があります(newのdeleteの場合、mallocのfreeの場合).具体的なコードは次の通りです(再帰と非再帰の2つの方法が含まれています).

#pragma once
#ifndef LIST_H
#define LIST_H

#include <iostream>

using namespace std;

struct ListNode
{
    int val;
    ListNode* next;

    ListNode():val(0),next(NULL){};
    ListNode(int value):val(value),next(NULL){};
};

//         
int InitList(ListNode* head)
{
    if (head ==NULL)
        return -1;

    ListNode* headBak = head;

    for (int i=1;i<10;i++)
    {
        ListNode* node = new ListNode(i);
        head->next = node;
        head = head->next;
    }

    for (int j=0;j<10;j++)
    {
        cout<<headBak->val<<"->";
        headBak = headBak->next;
    }
    cout<<endl;

    return 0;
}

//     --     
ListNode* ReverseLink(ListNode* head)
{
    ListNode* pPrev = NULL;
    ListNode* p = head;
    ListNode* pNext = NULL;

    //        
    if (head == NULL)
        return NULL;//     

    ListNode* pReverseHead = NULL;
    while (p !=NULL)
    {
        pNext = p->next;
        if (pNext == NULL)
            pReverseHead = p;

        p->next = pPrev;
        pPrev = p;
        p = pNext;
    }

    return pReverseHead;
}

//     --    
ListNode* ReverseList(ListNode* p, ListNode* &head)
{
    if (p == NULL || p->next == NULL)
    {
        head = p;
        return p;
    }
    else
    {
        ListNode* tmp = ReverseList(p->next,head);
        tmp->next = p;

        return p;
    }

    //0->1->2->3->4->5->6->7->8->9
    //      0->1,1->0
}

//         
int PrintReverseList(ListNode* head)
{
    if (head == NULL)
        return 0;

    PrintReverseList(head->next);
    cout<<head->val<<"->";
}

//              
int DeleteList(ListNode* head)
{
    if (head ==NULL)
        return 0;

    cout<<"    ：";

    ListNode* p = head;
    while (p != NULL)
    {
        ListNode* pTmp = p->next;

        cout<<p->val<<"->";

        delete(p);
        p = pTmp;
    }

    cout<<endl;

    return 0;
}

//    
void PrintNode(ListNode* node)
{
    for (;node!=NULL;)
    {
        cout<<node->val<<"->";
        node = node->next;
    }
    cout<<endl;
}
#endif

// ReverseLink.cpp :              。
//

#include "stdafx.h"
#include "list.h"

int _tmain(int argc, _TCHAR* argv[])
{
    ListNode* head = new ListNode();

    InitList(head);

    //        
    PrintReverseList(head);
    cout<cout<<"=============================="<//    
    ListNode* newHead = ReverseLink(head);

    PrintNode(newHead);
    cout<<"=============================="<cout<<"******************************"<new ListNode();
    PrintNode(newHead);
    cout<<"=============================="<//0->1->2->3->4->5->6->7->8->9
    //      0->1,1->0
    ListNode* pOldHead = ReverseList(newHead,h);
    pOldHead->next = NULL;
    PrintNode(h);
    cout<<"=============================="<//      
    DeleteList(head);

    return 0;
}