链表的创建，插入结点，删除结点等操作都只需要20行左右的代码来实现。 链表是一种动态数据结构，因为在创建链表的时候，无须知道链表的长度。当插入一个结点的时候，只需要为新结点分配内存，然后调整指针的指向来确保新结点被链接到链表当中。内存分配不是在创建链表的时候一次完成的，而是每添加一个结点分配一次内存。 如果单向链表的结点定义如下：
struct ListNode { int m_nValue; ListNode* m_pNext; }1.往链表的末尾中添加一个结点的代码如下：
void AddToTail(ListNode** pHead,int value) { ListNode* pNew=new ListNode(); pNew->m_nValue=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; } }2.由于链表中的内存不是一次性分配的，因此我们无法保证链表的内存和数组一样是连续的。因此，如果想在链表中找到它的第i个结点，我们只能从头结点开始，沿着指向下一个结点的指针遍历链表，它的时间效率为O(n)。而在数组中，我们可以根据下标在O(1)时间内找到第i个元素。 下面是在链表中找到第一个含有某值得结点并删除该结点的代码：
void RemoveNode(ListNode** pHead,int value) { if(pHead==NULL||*pHead==NULL) return; ListNode* pToBeDeleted=NULL: if((*pHead)->m_nValue==value) { pToBeDeleted=*pHead; *pHead=(*pHead)->m_pNext; } else { ListNode* pNode=*pHead; while(pNode->m_pNext!=NULL && pNode->m_pNext->m_nValue!=value) pNode=pNode->m_pNext; if(pNode->m_pNext!=NULL&& pNode->m_pNext->m_nValue==value) { pToBeDeleted=pNode->m_pNext； pNode->m_pNext=pNode->m_pNext->m_pNext; } } if(pToBeDeleted!=NULL) { delete pToBeDeleted; pToBeDeleted=NULL: } }题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。 分析： 通常打印是一个只读操作，不希望打印的时候修改内容。假设面试官也要求这个题目不能改变链表的结构。接下来想到的解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序是从尾到头的顺序。也就是第一个遍历到的结点最后一个输出，最后一个遍历到的结点第一个输出。这是典型的“后进先出”，可以用栈实现这种顺序。每进过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。 这种思路的代码如下：
void PrintListReversingly_Iteratively(ListNode* pHead) { std::stack<ListNode*> node; ListNode* pNode=pHead; while(pNode!=NULL) { nodes.push(pNode); pNode=pNode->m_pNext; } while(!nodes.empty()) { pNode=nodes.top(); printf("%d\t",pNode->m_nValue); nodes.pop(); } }既然想到了用栈来实现这个函数，而递归本质上就是一个栈结构。要实现反过来输出链表，我们每访问到一个结点的时候，就先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。 代码如下：
void PrintListReversingly_Recurisively(ListNode* pHead) { if(pHead!=NULL) { if(pHead->m_pNext!=NULL) { PrintListReversingly_Recurisively(pHead->m_pNext); } printf("%d\t",pHead->m_nValue); } }