（面试5）箭指offer之从尾到头打印链表

本文主要是介绍（面试5）箭指offer之从尾到头打印链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 1.单向链表的插入与删除
- 2.从尾到头打印链表

1.单向链表的插入与删除

往链表的末尾中添加一个节点

struct Listnode
{int m_Value;ListNode* m_pNext;
};当插入一个节点时，我们只需要为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表中
注意函数的第一个参数pHead是一个指向指针的指针，当我们往一个空链表中插入一个节点时，新插入的节点就是链表的头指针。
由于此时会改动头指针，所以必须把pHead参数设置为指向指针的指针，否则出了这个函数，pHead仍然是一个空指针
void AddtoTail(Listnode** pHead, int value)
{Listnode* pNew = new Listnode();pNew->m_Value = value;pNew->m_pNext = NULL;if (*pHead == NULL){*pHead = pNew;}else{Listnode* pNode = *pHead;while(pNode->m_pNext !=NULL){pNode = pNode->m_pNext;}pNode->m_pNext = pNew ;}}

在链表中找到第一个含有某值的节点并删除该节点的代码
（1）由于链表中的内存不是一次性分配的，所以无法保证链表的内存和数组一样是连续的
（2）若想在链表中找到它的第i个结点，只能从头结点开始遍历

void RemoveNode(List** pHead, int value)
{if (pHead == NULL || *pHead == NULL)return;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;}
}

2.从尾到头打印链表

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

/*******************************************************************
Copyright(c) 2016, Harry He
All rights reserved.Distributed under the BSD license.
(See accompanying file LICENSE.txt at
https://github.com/zhedahht/CodingInterviewChinese2/blob/master/LICENSE.txt)
*******************************************************************///==================================================================
// 《剑指Offer——名企面试官精讲典型编程题》代码
// 作者：何海涛
//==================================================================// 面试题6：从尾到头打印链表
// 题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。#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);}
}// ====================测试代码====================
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);
}int main(int argc, char* argv[])
{Test1();Test2();Test3();return 0;
}