- 从尾到头输出链表
Question：输入一个链表的头结点，从尾到头反过来打印出每个节点的值。
典型的后进先出，可以使用栈实现。
void Revers_Pring(ListNode* pHead) { std::stack<ListNode*> nodes; ListNode* pNode = pHead; while(pNode != NULL) { modes.push(pNode); pNode = pNode->pNext; } while(!nodes.empty()) { pNode = nodes.top(); printf("%d\t",pNode->data); nodes.pop(); } }递归本质上就是栈，所以也可以用递归实现
void ReversPrint(ListNode* pHead) { if(pHead!=NULL) { if(pHead->pNext != NULL) { ReversPrint(pHead->pNext); } printf("%d\t",pHead->data); } } - 在O(1)时间删除链表结点
题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。
分析：O(1)时间内把下一个节点的内存复制覆盖掉要删除的节点，并删除下一个节点。对于尾结点，仍需要顺序查找，复杂度O(n)。
以下代码前提假设为要删除的结点确实在链表中。
void DeleteNode(ListNode** pHead,ListNode* pDelete) { if(!pHead || !pDelete) return; //要删除的节点不是尾节点 if(pDelete->pNext!=NULL) { ListNode* Next = pDelete->pNext; pDelete->data = Next->data; pDelete->pNext = Next->pNext; delete Next; Next = NULL; } //链表只有一个节点 else if(*pHead == pDelete) { delete pDelete; pDelete = NULL; *pHead = NULL; } //链表中有多个节点，删除尾节点，需要顺序查找 else { ListNode *Node = *pHead; while(Node->pNext!=pDelete) Node = Node->pNext; Node->pNext = NULL; delete pDelete; pDelete = NULL; } } - 链表中的倒数第k个结点
题目：输入一个链表，输出该链表中倒数第k个结点。假设链表的尾节点为倒数第一个结点。
分析：两个指针差k-1步，但需要注意特殊情况：Head为空指针，结点数少于k个，参数k=0情况。
延伸：求链表中间结点。定义两个指针，一个指针一次一步，一个指针一次两步，走得快的到尾部时，走的慢的正好在中间。同样，判断单向链表是否形成了环形，也是这样，最后如果走得快的指针追上了走得慢的指针，那么链表就是环形链表，如果走得快的走到了链表尾部都没有追上慢的，那么就不是环形链表。
ListNode* FindKthToTail(ListNode* pHead,int k) { if(pHead == NULL || k < 0) return NULL; ListNode* pA = pHead;//先移动k-1步 ListNode* pB = pHead; for(int i = 0;i < k-1;++i) { if(pA == NULL) return NULL; else pA = pA->pNext; } while(pA->pNext!=NULL) { pA = pA->pNext; pB = pB->pNext; } return pB; } - 反转链表
题目：定义一个函数，输入一个链表的头指针，反转该链表并输出反转后链表的头结点。
分析：为防止链表断开，需定义三个指针，分别指向当前遍历到的结点、它的前一个结点及后一个结点。
ListNode* ReverseList(ListNode* pHead) { ListNode* ReversedHead = NULL; ListNode* Node = pHead; ListNode* Prev = NULL; //头结点反转后指向NULL while(Node != NULL) { ListNode* Next = Node->pNext; //指向后一个结点 if(Next == NULL) ReversedHead = Node; Node->pNext = Prev; Prev = Node; Node = Next; } return ReversedHead; } - 合并两个排序的链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
ListNode* Merge(ListNode* pHead1,ListNode* pHead2) { if(pHead1 == NULL) return pHead2; if(pHead2 == NULL) return pHead1; ListNode* pMerge = NULL; if(pHead1->data < pHead2->data) { pMerge = pHead1; pMerge->pNext=Merge(pHead1->pNext,pHead2); } else { pMerge = pHead2; pMerge->pNext=Merge(pHead1,pHead2->pNext); } return pMerge; } - 两个链表的第一个公共结点（还有树的公共结点问题）
题目：输入两个链表，找出它们的第一个公共结点。
分析：如果两个链表有公共结点，那么公共结点出现在两个链表的尾部。从两个尾部开始向前比较，最后一个相同的借点就是我们要找的结点。分别将两个链表的结点放入两个栈，每次比较栈顶结点，相同就弹出比较下一个。（需要复制空间）
或者我们先遍历一遍得到两个链表的长度，然后让长的链表先向前走几步，之后再同时遍历。
- 环形链表-圆圈中最后剩下的数字
题目：0,1,2，…n-1这n个数排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字，求出这个圆圈中最后剩下的那个数字（约瑟夫问题）。例如，{0,1,2,3,4}从0开始删除第3个数字，那么删除的前四个数依次是2,0,4,1，最后剩下3.
解法一：环形链表模拟
用std::list模仿环形链表，扫描到链表尾部时记得吧迭代器移到头部。int LastRemain(unsigned int n,unsigned int m) { if(n<1||m<1) return -1; list<int> numbers; for(int i=0;i<n;++i) numbers.push_back(i); list<int>::iterator cur = numbers.begin(); while(numbers.size()>1) { for(int i=1;i<m;++i) { cur++; if(cur == numbers.end()) cur = numbers.begin(); } list<int>::iterator next = ++cur; if(next == numbers.end()) next = numbers.begin(); --cur; numbers.erase(cur); cur=next; } return *(cur); }解法二：分析每次被删除的数字的规律直接计算出最后剩下的数字
1) if we shift the ids by k, namely, start from k instead of 0, we should add the result by k%n
2) after the first round, we start from k+1 ( possibly % n) with n-1 elements, that is equal to an (n-1) problem
while start from (k+1)th element instead of 0, so the answer is (f(n-1, m)+k+1)%n
3) k = m-1, so f(n,m)=(f(n-1,m)+m)%n.
finally, f(1, m) = 0;Now this is a O(n) solution.
int LastRemain(unsigned 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; } - 二叉搜索树与双向链表
题目：输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建新的结点，只能调整树中节点指针的指向。
分析：中序遍历，当遍历到根节点时，连接左子链表的最右结点和右子链表的最左结点。再递归调整左右子链表。
struct BinaryTreeNode { int nValue; BinaryTreeNode* pLeft; BinaryTreeNode* pRight; }; void helper(BinaryTreeNode *&head,BinaryTreeNode *&tail,BinaryTreeNode *root) { BinaryTreeNode *lt,*rh; //left tail,right head if(root == NULL) { head = NULL; tail = NULL; return; } helper(head,lt,root->pLeft); helper(rh,tail,root->pRight); if(lt != NULL) { lt->pRight = root; root->pLeft = lt; } else head = root; if(rh != NULL) { root->pRight = rh; rh->pLeft = root; } else tail = root; } BinaryTreeNode* treeToLinkedList(BinaryTreeNode *root) { BinaryTreeNode *head,*tail;//生成双向链表的头指针和尾指针 helper(head,tail,root); return head; } - 复杂链表的复制
题目：实现函数ComplexListNode* Clone(ComplexListNode* pHead),复制一个复杂链表。复杂链表中，每个结点除了有一个指针指向下一个结点，还有一个指针指向链表中任意结点或者NULL。
分析：
struct ComplexNode { int m_nValue; ComplexNode* m_pNext; ComplexNode* m_pSibling; }; ComplexNode* Clone(ComplexNode* pHead) { if (pHead == NULL) return NULL; preClone(pHead); inClone(pHead); return postClone(pHead); } void preClone(ComplexNode* pHead) { //复制原始链表的任意结点N并创建新结点N’,链接到N的后面 ComplexNode* pNode = pHead; while(pNode != NULL) { ComplexNode* pClone = new ComplexNode(); pClone->m_nValue = pNode->m_nValue; pClone->m_pNext = pNode->m_pNext; pClone->m_pSibling = NULL; pNode->m_pNext = pClone; pNode = pClone->m_pNext; } } void inClone(ComplexNode* pHead) { //原始链表上的节点N的m_pSibling指向S，则N'指向S的下一个节点S' ComplexNode * pNode = pHead; while(pNode != NULL) { ComplexNode* pClone = pNode->m_pNext; if(pNode->m_pSibling != NULL) pClone->m_pSibling = pNode->m_pSibling->m_pNext; pNode = pClone->m_pNext; } } ComplexNode * postClone(ComplexNode* pHead) { //拆分链表，奇偶 ComplexNode* pNode = pHead; ComplexNode* pCloneHead = NULL; ComplexNode* pCloneNode = NULL; if(pNode != NULL) { pCloneHead = pCloneNode = pNode->m_pNext; pNode->m_pNext = pCloneNode->m_pNext; pNode = pNode->m_pNext; } while(pNode != NULL) { pCloneNode->m_pNext = pNode->m_pNext; pCloneNode = pCloneNode->m_pNext; pNode->m_pNext = pCloneNode->m_pNext; pNode = pNode->m_pNext; } return pCloneHead; } - 从一个未排序的单链表中删除重复元素
题目：Write code to remove duplicates from an unsorted linked list.
解法一：如果对空间复杂度没有要求，则使用哈希表，如果存在即删除，如果不存在将值写入hashtable。
解法二：使用两个pointer进行遍历–current进行正常遍历，当runner每次从头开始查找(到current为止)是否有重复元素，如果重复，删除current。
void deleteDups(ListNode* pHead) { if(pHead == NULL) return; ListNode* pre = pHead; ListNode* current = pre->pNext; while(current != NULL) { ListNode* runner = pHead; while(runner != current) { if(runner->data == current->data) { //remove current ListNode* tmp = current->pNext; pre->pNext = tmp; current = tmp; break;//跳出的while循环 } runner = runner->pNext; } if(runner == current) { //runner在0-current间遍历 //无重复 pre = current; current = current->pNext; } } } - You have two numbers represented by a linked list,where each node contains a single digit.The digits are stored in reverse order,such that the 1’s digit is at the head of the list.Write a function that adds the two numbers and returns the sum as a linked list.e.g. Input:(3->1->5),(5->9->2),Output:8->0->8
分析：每一位的值相当于(链表1的值+链表2的值+前一位的进位)%10，如果该位所得的值超过10，带进位。ListNode* addLists(ListNode* p1,ListNode* p2,int flag) { if(p1==NULL && p2==NULL) return NULL; ListNode* result; int value = flag; if(p1!=NULL) value += p1->data; if(p2!=NULL) value += p2->data; result->data = value%10; ListNode* more = addLists(p1 == NULL?NULL:p1->pNext, p2==NULL?NULL:p2->pNext, value>10?1:0); result->pNext = more; return result; } - Given a circular linked list,implement an algorithm which returns node at the beginning of the loop.e.g. Input:A->B->C->D->E->C,output:C.
分析：两个指针，一个每次移动1步，一个每次移动2步，如果最后能相遇，则表明链表有环。
1)表头距离环开始处k个结点；2)p1p2相遇处距离环开始处也为k个结点；3)寻找两个点的中点即可。ListNode* FindBeginning(ListNode* pHead) { ListNode* p1 = pHead; ListNode* p2 = pHead; while(p2->pNext!=NULL) { p1=p1->pNext; p2=p2->pNext->pNext; if(p1==p2) break; } if(p2->pNext==NULL) return NULL;//no loop p1 = pHead; while(p1!=p2) { p1=p1->pNext; p2=p2->pNext; } return p2; }