剑指offer--面试题5

时间：2023-03-10 01:24:03
剑指offer--面试题5

到现在为止，看过的书+代码有一定量了，并且也参加了个比赛，给自己的总体感觉：编程需要的是灵活的头脑，书里的东西只是讲个规则、思想，其实际实现可以千差万别！   潜在的规则+灵活的思维 = 程序！

在做面试题5时，发现Utilities文件夹下的内容太好了，基本上是那些数据结构的实现：链表、二叉树、树等（缺个图），准备通过学习这些代码来深入理解各个数据结构及其接口/成员函数。

拿该题来说，解决单链表！！！

题目：逆序打印单链表

一、自己写单链表类及其操作

花了一下午时间，无语了。。。

1、List.h

//单链表数据结构及基本操作

//最大节点数

const int MAXLENGTH = ;

//节点

struct ListNode

{

    int m_Value;

    ListNode* m_pNext;

};

//List类

class List

{

private:

    ListNode LNode;

    int MaxLength;

public:

    //constructor and deconstructor

    List();

    virtual ~List();

    //单链表操作

    //1. 创建节点

    ListNode* CreateListNode(int value);

    //2. 创建链表或者将节点加到链尾

    void CreateFrontOrAddToTail(ListNode** pHead, int value);

    //3. 在第i个节点之前插入新的节点

    void ListInsert(ListNode* pHead, int i, int value);

    //4. 删除value=e的节点

    void RemoveListNode(ListNode** pHead,int value);

    //5. 查找第一个value=e的节点

    int FindListNode(ListNode* pHead,int value);

    //6. 销毁链表

    void DestoryList(ListNode* pHead);

    //7. 链表元素个数

    int ListLength(ListNode* pHead);

};

2、List.cpp

//List.cpp

#include "List.h"

#include <iostream>

List::List()

{

    LNode.m_Value = ;

    LNode.m_pNext = NULL;

    MaxLength = MAXLENGTH;

}

List::~List()

{

}

    //1. 创建节点

ListNode* List::CreateListNode(int value)

{

    ListNode* pNew = new ListNode;

    pNew->m_Value = value;

    pNew->m_pNext = NULL;

}

    //2. 创建链表或者将节点加到链尾

void List::CreateFrontOrAddToTail(ListNode** pHead, int value)

{

    if(pHead == NULL)

        return;

    ListNode* pNew = CreateListNode(value);

    if(*pHead == NULL) //空链表

        *pHead = pNew;

    else

    {

        ListNode* pNode = *pHead;

        while(pNode->m_pNext != NULL)

            pNode = pNode->m_pNext;

        pNode->m_pNext = pNew;

    }

}

    //3. 在第i个节点之前插入新的节点

void List::ListInsert(ListNode* pHead, int i, int value)

{

    if(pHead == NULL || i >= MaxLength)

        return;

    ListNode* pNew = CreateListNode(value);

    ListNode* pNode = *pHead;

    ListNode* preNode = *pHead;

    i--;

    while(i && pNode->m_pNext != NULL)

    {

        preNode = pNode;

        pNode = pNode->m_pNext;

        i--;

    }

    if(i == )

    {

        preNode->m_pNext = pNew;

        pNew->m_pNext = pNode;

    }

    else

        cout<<"Failed!"<<endl;

}

    //4. 删除value=e的第一个节点

bool List::RemoveListNode(ListNode** pHead,int value)

{

    if(pHead == NULL || *pHead == NULL)

        return false;

    ListNode* pToBeDeleted = NULL;

    if((*pHead)->m_Value == value)

    {

        pToBeDeleted = *pHead;

        *pHead = (*pHead)->m_pNext;

    }

    else

    {

        ListNode* pNode = *pHead;

        while(pNode->m_pNext != NULL &&　pNode->m_pNext->m_Value != value)

            pNode = pNode->m_pNext;

        if(pNode->m_pNext != NULL &&　pNode->m_pNext->m_Value == value)

        {

            pToBeDeleted = pNode->m_pNext;

            pNode->m_pNext = pNode->m_pNext->m_pNext;

        }

    }

    if(pToBeDeleted != NULL)

    {

        delete pToBeDeleted;

        pToBeDeleted = NULL;

        return true;

    }

        return false;

}

    //5. 查找第一个value=e的节点,返回其位置

int List::FindListNode(ListNode* pHead,int value)

{

    int i = ;

    ListNode* pNode = pHead;

    while(pNode != NULL && pNode->m_Value != value)

    {

        i++;

        pNode = pNode->m_pNext;

    }

    if(pNode != NULL && pNode->m_Value == value)

        return i;

    else

        return ;

}

    //6. 销毁链表

void List::DestoryList(ListNode* pHead)

{

    ListNode* pNode = pHead;

    while(pHead != NULL)

    {

        pNode = pHead;

        pHead = pHead->m_pNext;

        delete pNode;

    }

}

    //7. 链表元素个数

int List::ListLength(ListNode* pHead)

{

    ListNode* pNode = pHead;

    int i = ;

    while(pNode != NULL)

    {

        i++;

        pNode = pNode->m_pNext;

    }

    return i;

}

未测试过。。。因为想继续做面试题5了，进度太慢了！！！

二、面试题5整理：

逆序打印单链表，首先想到的便是通过扫描链表，并同时用栈存储每个值，最后利用栈的LIFO特点打印即可。但是，鉴于自己的水平，并没有用过C++中stl里的stack，因此想了另一种方法，即将扫描链表时所得到的值存入到一个数组中，最后逆序打印即可。这种方法固然可行，但效率上必然低于栈的。所以综合以上分析，又学习了stl中的stack，具体见上一篇博客。最后，怎么也没想到可以用递归的方式求解。。。

根据作者代码思想，做了如下改动：

void PrintListReversingly_Iteratively(ListNode* pHead)

{

    std::stack<int> nodes;

    ListNode* pNode = pHead;

    while(pNode != NULL)

    {

        nodes.push(pNode->m_nValue);

        pNode = pNode->m_pNext;

    }

    int value;

    while(!nodes.empty())

    {

        value = nodes.top();

        printf("%d\t", value);

        nodes.pop();

    }

}

这里将stack的元素设置为了m_nValue的类型，仔细想想后，认为还是原代码更合理，原因如下：

原代码中，节点地址入栈，因此栈中每个元素所占存储是固定的，在32位操作系统下，指针（地址）占4字节；但如果存储的是节点数据元素，那么每个元素所占存储很可能大于4字节；

void PrintListReversingly_Recursively(ListNode* pHead)

{

    if(pHead == NULL)

    {

        return;

    }

    else

    {

        PrintListReversingly_Recursively(pHead->m_pNext);

        printf("%d\t", pHead->m_nValue);

    }

}

相关文章