剑指offer笔记面试题6----从未到头打印链表

题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。链表节点定义如下：

struct ListNode{

	int m_nKey;

	ListNode* m_pNext;

}

测试用例：

功能测试（输入的链表有多个节点；输入的链表只有一个节点）。
特殊输入测试（输入的链表头结点指针为nullptr）。

测试代码：

void Test(ListNode* pHead)

{

    PrintList(pHead);

    PrintListReversingly_Iteratively(pHead);

    printf("\n");

    PrintListReversingly_Recursively(pHead);

}

// 1->2->3->4->5

void Test1()

{

    printf("\nTest1 begins.\n");

    ListNode* pNode1 = CreateListNode(1);

    ListNode* pNode2 = CreateListNode(2);

    ListNode* pNode3 = CreateListNode(3);

    ListNode* pNode4 = CreateListNode(4);

    ListNode* pNode5 = CreateListNode(5);

    ConnectListNodes(pNode1, pNode2);

    ConnectListNodes(pNode2, pNode3);

    ConnectListNodes(pNode3, pNode4);

    ConnectListNodes(pNode4, pNode5);

    Test(pNode1);

    DestroyList(pNode1);

}

// 只有一个结点的链表: 1

void Test2()

{

    printf("\nTest2 begins.\n");

    ListNode* pNode1 = CreateListNode(1);

    Test(pNode1);

    DestroyList(pNode1);

}

// 空链表

void Test3()

{

    printf("\nTest3 begins.\n");

    Test(nullptr);

}

本题考点：

考查应聘者对单向链表的理解和编程能力。
考查应聘者对循环、递归和栈3个相互关联的概念的理解。

实现代码：

/***********************************List.h*********************************/

struct ListNode

{

    int       m_nValue;

    ListNode* m_pNext;

};

ListNode* CreateListNode(int value);

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext);

void PrintListNode(ListNode* pNode);

void PrintList(ListNode* pHead);

void DestroyList(ListNode* pHead);

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

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

/*************************************List.cpp***********************************/

#include "list.h"

#include <stdio.h>

#include <stdlib.h>

ListNode* CreateListNode(int value)

{

    ListNode* pNode = new ListNode();

    pNode->m_nValue = value;

    pNode->m_pNext = nullptr;

    return pNode;

}

void ConnectListNodes(ListNode* pCurrent, ListNode* pNext)

{

    if(pCurrent == nullptr)

    {

        printf("Error to connect two nodes.\n");

        exit(1);

    }

    pCurrent->m_pNext = pNext;

}

void PrintListNode(ListNode* pNode)

{

    if(pNode == nullptr)

    {

        printf("The node is nullptr\n");

    }

    else

    {

        printf("The key in node is %d.\n", pNode->m_nValue);

    }

}

void PrintList(ListNode* pHead)

{

    printf("PrintList starts.\n");

    ListNode* pNode = pHead;

    while(pNode != nullptr)

    {

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

        pNode = pNode->m_pNext;

    }

    printf("\nPrintList ends.\n");

}

void DestroyList(ListNode* pHead)

{

    ListNode* pNode = pHead;

    while(pNode != nullptr)

    {

        pHead = pHead->m_pNext;

        delete pNode;

        pNode = pHead;

    }

}

void AddToTail(ListNode** pHead, int value)

{

    ListNode* pNew = new ListNode();

    pNew->m_nValue = value;

    pNew->m_pNext = nullptr;

    if(*pHead == nullptr)

    {

        *pHead = pNew;

    }

    else

    {

        ListNode* pNode = *pHead;

        while(pNode->m_pNext != nullptr)

            pNode = pNode->m_pNext;

        pNode->m_pNext = pNew;

    }

}

void RemoveNode(ListNode** pHead, int value)

{

    if(pHead == nullptr || *pHead == nullptr)

        return;

    ListNode* pToBeDeleted = nullptr;

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

    {

        pToBeDeleted = *pHead;

        *pHead = (*pHead)->m_pNext;

    }

    else

    {

        ListNode* pNode = *pHead;

        while(pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue != value)

            pNode = pNode->m_pNext;

        if(pNode->m_pNext != nullptr && pNode->m_pNext->m_nValue == value)

        {

            pToBeDeleted = pNode->m_pNext;

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

        }

    }

    if(pToBeDeleted != nullptr)

    {

        delete pToBeDeleted;

        pToBeDeleted = nullptr;

    }

}

/***************************PrintlistInReversedOrder.cpp******************************/

#include "..\Utilities\List.h"

#include <stack>

void PrintListReversingly_Iteratively(ListNode* pHead)

{

    std::stack<ListNode*> nodes;

    ListNode* pNode = pHead;

    while(pNode != nullptr)

    {

        nodes.push(pNode);

        pNode = pNode->m_pNext;

    }

    while(!nodes.empty())

    {

        pNode = nodes.top();

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

        nodes.pop();

    }

}

void PrintListReversingly_Recursively(ListNode* pHead)

{

    if(pHead != nullptr)

    {

        if (pHead->m_pNext != nullptr)

        {

            PrintListReversingly_Recursively(pHead->m_pNext);

        }

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

    }

}

int main()

{

    Test1();

    Test2();

    Test3();

	int a;

	scanf("%d", &a);

    return 0;

}

巴特西

剑指offer笔记面试题6----从未到头打印链表

题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。链表节点定义如下：

测试用例：

测试代码：

本题考点：

实现代码：

最新文章

热门文章