数据结构和算法，是我们程序设计最重要的两大元素，可以说，我们的编程，都是在选择和设计合适的数据结构来存放数据，然后再用合适的算法来处理这些数据。
在面试中，最经常被提及的就是链表，因为它简单，但又因为需要对指针进行操作，凡是涉及到指针的，都需要我们具有良好的编程基础才能确保代码没有任何错误。
链表是一种动态的数据结构，因为在创建链表时，我们不需要知道链表的长度，当插入一个结点时，只需要为该结点分配内存，然后调整指针的指向来确保新结点被连接到链表中。所以，它不像数组，内存是一次性分配完毕的，而是每添加一个结点分配一次内存。正是因为这点，所以它没有闲置的内存，比起数组，空间效率更高。
像是单向链表的结点定义如下：
struct ListNode {int m_nValue;ListNode* m_pNext; }；
那么我们往该链表的末尾添加一个结点的代码如：
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;} }
我们传递一个链表时，通常是传递它的头指针的指针。当我们往一个空链表插入一个结点时，新插入的结点就是链表的头指针，那么此时就会修改头指针，因此必须把pHead参数设置为指向指针的指针，否则出了这个函数，pHead指向的依然是空，因为我们传递的会是参数的一个副本。但这里又有一个问题，为什么我们必须将一个指向ListNode的指针赋值给一个指针呢？我们完全可以直接在函数中直接声明一个ListNode而不是它的指针？注意，ListNode的结构中已经非常清楚了，它的组成中包括一个指向下一个结点的指针，如果我们直接声明一个ListNode，那么我们是无法将它作为头指针的下一个结点的，而且这样也能防止栈溢出，因为我们无法知道ListNode中存储了多大的数据，像是这样的数据结构，最好的方式就是传递指针，这样函数栈就不会溢出。
对于java程序员来说，指针已经是遥远的记忆了，因为java完全放弃了指针，但并不意味着我们不需要学习指针的一些基础知识，毕竟这个世界上的代码并不全部是由java所编写，像是C/C++的程序依然运行在世界上大部分的机器上，像是一些系统的源码，就是用它们编写的，加上如果我们想要和底层打交道的话，学习C/C++是必要的，而指针就是其中一个必修的内容。
就因为链表的内存不是一次性分配的，所以它并不像数组一样，内存是连续的，所以如果我们想要在链表中查找某个元素，我们就只能从头结点开始，而不能像数组那样根据索引来，所以时间效率为O(N)。
像是这样：
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(ListNode* pHead) {std :: stack<ListNode*> nodes;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(ListNode* pHead) {if(pHead != NULL){if(pHead->m_pNext != NULL){PrintListReversingly(pHead->m_pNext);}printf("%d\t", pHead->m_nValue);} }
但使用递归就意味着可能发生栈溢出的风险，尤其是链表非常长的时候。所以，基于循环实现的栈的鲁棒性要好一些。
利用栈来解决链表问题是非常常见的，因为单链表的特点是只能从头开始遍历，如果题目要求或者思路要求从尾结点开始遍历，那么我们就可以考虑使用栈，因为它符合栈元素的特点：先进后出。
链表的逆序是经常考察到的，因为要解决这个问题，必须要反过来思考，从而能够考察到面试者是否具有逆思维的能力。
题目二：定义一个函数，输入一个链表的头结点，然后反转该链表并输出反转后链表的头结点。
和上面一样，我们都要对链表进行逆序，但不同的是这次我们要改变链表的结构。
最直观的的做法就是：遍历该链表，将每个结点指向前面的结点。但这种做法会有个问题，举个例子：我们一开始将头指针指向NULL,也就是说，pHead->next = NULL,但是获取后面结点的方法是：pHead->next->next，这时会是什么呢？pHead->next已经是NULL,NULL->next就是个错误！所以，我们自然就想到，要在遍历的时候保留pHead->next。
ListNode* ReverseList(ListNode* pHead) {ListNode* pReversedHead = NULL;ListNode* pNode = pHead;ListNode* pPrev = NULL;while(pNode != NULL){ListNode* pNext = pNode->m_pNext;if(pNext == NULL){pReversedHead = pNode;}pNode->m_pNext = pPrev;pPrev = pNode;pNode = pNext;}return pReversedHead; }
从最直观的的做法开始，一步一步优化，并不是每个人都能第一时间想到最优解，要让代码在第一时间内正确的运行才是首要的，然后在不影响代码的外观行为下改进代码。
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {if(pListHead == NULL || k == 0){return NULL;}ListNode* pAhead = pListHead;ListNode* pBehind = NULL;for(unsigned int i = 0; i < k - 1; ++i){if(pAhead->m_pNext != NULL){pAhead = pAhead->m_pNext;}else{return NULL;}}pBehind = pListHead;while(pAhead->m_pNext != NULL){pAhead = pAhead->m_pNext;pBehind = pBehind->m_pNext;}return pBehind; }
鲁棒性是非常重要的，所以在考虑一个问题的时候必须充分考虑各种情况，不要一开始想到思路就开始写代码，最好是先想好测试用例，然后再让自己的代码通过所有的测试用例。
使用栈最大的问题就是空间复杂度，像是下面这道题目：
题目四：输入两个链表，找出它们的第一个公共结点。
拿到这道题目，我们的第一个想法就是在每遍历一个链表的结点时，再遍历另一个链表。这样大概的时间复杂度将会是O(M * N)。如果是数组，或许我们可以考虑一下使用二分查找来提高查找的效率，但是链表完全不能这样。
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {unsigned int len1 = GetListLength(pHead1);unsigned int len2 = GetListLength(pHead2);int lengthDif = len1 - len2;ListNode* pListHeadLong = pHead1;ListNode* pListHeadShort = pHead2;if(len2 > len1){pListHeadLong = pHead2;pListHeadShort = pHead1;lengthDif = len2 - len1;}for(int i = 0; i < lengthDif; ++i){pListHeadLong = pListHeadLong->m_pNext;}while((pListHeadLong != NULL) && (pListHeadShort != NULL) && (pListHeadLong != pListHeadShort)){pListHeadLong = pListHeadLong->m_pNext;pListHeadShort = pListHeadShort->m_pNext;}ListNode* pFirstCommonNode = pListHeadLong;return pFirstCommonNode; }unsigned int GetListLength(ListNode* pHead) {unsigned int length = 0;ListNode* pNode = pHead;while(pNode != NULL){++length;pNode = pNode->m_pNext;}return length; }
就算是链表的基本操作，也会作为面试题目出现，这时就要求我们能够写出更快效率的代码出来，像是下面这道题目：
题目五：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。
这个题目的要求是让我们能够像数组操作一样，实现O(1)，而根据一般链表的特点，是无法做到这点的，这就要求我们想办法改进一般的删除结点的做法。
一般我们删除结点，就像上面的做法，是从头指针开始，然后遍历整个链表，之所以要这样做，是因为我们需要得到将被删除的结点的前面一个结点，在单向链表中，结点中并没有指向前一个结点的指针，所以我们才从链表的头结点开始按顺序查找。
知道这点后，我们就可以想想其中的一个疑问：为什么我们一定要得到将被删除结点前面的结点呢？事实上，比起得到前面的结点，我们更加容易得到后面的结点，因为一般的结点中就已经包含了指向后面结点的指针。我们可以把下一个结点的内容复制到需要删除的结点上覆盖原有的内容，再把下一个结点删除，那其实也就是相当于将当前的结点删除。
根据这样的思路，我们可以写：
void DeleteNode(LisNode** pListHead, ListNode* pToDeleted) {if(!pListHead || !pToBeDeleted){return;}if(pToBeDeleted->m_pNext != NULL){ListNode* pNext = pToBeDeleted->m_pNext;pToBeDeleted->m_nValue = pNext->m_nValue;pToBeDeleted->m_pNext = pNext->m_pNext;delete pNext;pNext = NULL;}else if(*pListHead == pToBeDeleted){delete pToBeDeleted;pToBeDeleted = NULL;*pListHead = NULL;}else{ListNode* pNode = *pListHead;while(pNode->m_pNext != pToBeDeleted){pNode = pNode->m_pNext;}pNode->m_pNext = NULL;delete pToBeDeleted;pToBeDeleted = NULL;} }
首先我们需要注意几个特殊情况：如果要删除的结点位于链表的尾部，那么它就没有下一个结点，这时我们就必须从链表的头结点开始，顺序遍历得到该结点的前序结点，并完成删除操作。还有，如果链表中只有一个结点，而我们又要删除；；链表的头结点，也就是尾结点，这时我们在删除结点后，还需要把链表的头结点设置为NULL，这种做法重要，因为头指针是一个指针，当我们删除一个指针后，如果没有将它设置为NULL,就不能算是真正的删除该指针。
我们接着分析一下为什么该算法的时间复杂度为O(1)。
对于n- 1个非尾结点而言，我们可以在O(1)时把下一个结点的内存复制覆盖要删除的结点，并删除下一个结点，但对于尾结点而言，由于仍然需要顺序查找，时间复杂度为O(N)，因此总的时间复杂度为O[((N - 1) * O(1) + O(N)) / N] = O(1)，这个也是需要我们会计算的，不然我们无法向面试官解释，为什么这段代码的时间复杂度就是O(1)。
上面的代码还是有缺点，就是基于要删除的结点一定在链表中，事实上，不一定，但这份责任是交给函数的调用者。
题目六：输入两个递增链表，合并为一个递增链表。
这种题目最直观的做法就是将一个链表的值与其他链表的值一一比较。考察链表的题目不会要求我们时间复杂度，因为链表并不像是数组那样，可以方便的使用各种排序算法和查找算法。因为链表涉及到大量的指针操作，所以链表的题目考察的主要是两个方面：代码的鲁棒性和简洁性。
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {if(pHead1 == NULL){return pHead2;}else if(pHead == NULL){return pHead1;}ListNode* pMergedHead = NULL;if(pHead->m_nValue < pHead->m_nValue){pMergedHead = pHead1;pMergedHead->m_pNext = Merge(pHead->m_pNext, pHead2);}else{pMergedHead = pHead2;pMergedHead->m_pNext = Merge(pHead1, pHead2->m_pNext);}return pMergedHead; }
到现在为止，我们的链表都是单链表，并且结点的定义都是一般链表的定义，但如果面对的是自定义结点组成的链表呢？
struct ComplexListNode {int m_nValue;ComplexListNode* m_pNext;ComplexListNode* m_pSibling; };
题目七：请实现一个函数实现该链表的复制，其中m_pSibling指向的是链表中任意一个结点或者NULL。
这种题目就要求我们具有发现规律的能力了。
复制链表并不难，但是我们会想到效率的问题。
ComplexListNode* Clone(ComplexListNode* pHead) {CloneNodes(pHead);ConnectSiblingNodes(pHead);return ReconnectNodes(pHead); }void CloneNodes(ComplexListNode* pHead) {ComplexListNode* pNode = pHead;while(pNode != NULL){ComplexListNode* pCloned = new ComplexListNode();pCloned->m_nValue = pNode->m_nValue;pCloned->m_pNext = pNode->m_pNext;pCloned->m_pSibling = NULL;pNode->m_pNext = pCloned;pNode = pCloned->m_pNext;} }void ConnectSiblingNode(ComplexListNode* pHead) {ComplexListNode* pNode = pHead;while(pNode != NULL){ComplexListNode* pCloned = pNode->m_pNext;if(pNode->m_pSibling != NULL){pCloned->m_pSibling = pNode->m_pSibling->m_pNext;}pNode = pCloned->m_pNext;} }ComplexListNode* ReconnectNode(ComplexListNode* pHead) {ComplexListNode* pNode = pHead;ComplexListNode* pClonedHead = NULL;ComplexListNode* pClonedNode = NULL;if(pNode != NULL){pClonedHead = pClonedNode = pNode->m_pNext;pNode->m_pNext = pClonedNode->m_pNext;pNode = pNode->m_pNext;}while(pNode != NULL){pClonedNode->m_pNext = pNode->m_pNext;pClonedNode = pClonedNode->m_pNext;pNode->m_pNext = pClonedNode->m_pNext;pNode = pNode->m_pNext;}return pClonedHead; }
int LastRemaining(unsigned int n, unsigned int m) {if(n < 1 || m < 1){return -1;}unsigned int i = 0;lisg<int> numbers;for(i = 0; i < n; ++i){numbers.push_back(i);}list<int> :: iterator current = numbers.begin();while(numbers.size() > 1){for(int i = 1l i < m; ++i){current++;if(current == numbers.end()){current = number.begin();}}list<int> :: iterator next = ++current;if(next == numbers.end()){next = numbers.begin();}--current;numbers.erase(current);current = next;}return *(current); }
int LastRemaining(unsigned int n, unsigned int m) {if(n < 1 || m < 1){return -1;}unsigned int i = 0;lisg<int> numbers;for(i = 0; i < n; ++i){numbers.push_back(i);}list<int> :: iterator current = numbers.begin();while(numbers.size() > 1){for(int i = 1l i < m; ++i){current++;if(current == numbers.end()){current = number.begin();}}list<int> :: iterator next = ++current;if(next == numbers.end()){next = numbers.begin();}--current;numbers.erase(current);current = next;}return *(current); }
我们可以用std :: list来模拟一个环形链表，但因为std :: list本身并不是一个环形结构，所以我们还要在迭代器扫描到链表末尾的时候，把迭代器移到链表的头部。
如果是使用数学公式的话，代码就会非常简单：
int LastRemaining(unsigend int n, unsigned int m) {if(n < 1 || m < 1){return -1;}int last = 0;for(int i = 2; i <= n; ++i){last = (last + m) % i;}return last; }
这就是数学的魅力，并且它的时间复杂度是O(N),空间复杂度是O(1)。