首页 » C++ » 实现单链表反转

实现单链表反转

原文 http://blog.csdn.net/soygrow/article/details/79230085

2018-02-02 02:01:02阅读(321)

实现单链表反转主要思路:

三个节点,开始时中间节点指向头结点,第一个节点指向NULL,第三个节点指向头结点下个节点。 将中间节点反转 三个节点均向后移动一格 判断是否是结束条件

需要注意的是:链表在使用结束后,需要释放内存(如果是new的要delete,malloc的要free)
具体代码如下所示(包含递归和非递归两种方法):

#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<<endl;
    cout<<"=============================="<<endl;
    //倒置链表
    ListNode* newHead = ReverseLink(head);
    PrintNode(newHead);
    cout<<"=============================="<<endl<<endl;;
    cout<<"******************************"<<endl;
    ListNode* h = new ListNode();
    PrintNode(newHead);
    cout<<"=============================="<<endl;
    //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<<"=============================="<<endl;
    //链表释放内存
    DeleteList(head);
    return 0;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹