（1）从尾到头打印链表
算法思路：（1）递归（2）借助栈（剑指offer6题）
（2）O(1)时间内删除链表节点
算法思路：常规解法：从头开始遍历，找到待删除节点的前一个节点，然后接到待删除节点的下一个节点。但是时间复杂度是O(n);其他解法：找到待删除节点的下一个节点，把它复制给待删除节点，并删除自己。
（3）打印链表倒数第k个节点的元素
算法思路：定义两个指针，一个在另一个前k个节点，每一移动1位，当一个到达尾部时，另一个到达倒数第k个。判空，判长度有没有k.
（4）求链表的中间节点
算法思路：定义两个指针，从头结点开始，一个一次走两步，一个一次走一步，走的快的到达终点时，慢的到达中间位置。快慢指针。
（5）链表中环的入口
算法思路：使用快慢指针，一个走一步，一个走两步，如果慢的可以追上快的，则说明有环。以相遇的节点开始计数，再次相遇时停止计数，计数值为环的大小。仍然为一个走1步，一个每次走两步。
若环的大小为n,则定义两个指针，一个在另一个前n步。以相同速度移动，相遇时，到达入口。
（6）合并两个有序链表
算法思路：递归，使用归并的方法。先比较两个链表的头结点，最小的为新的头结点，然后在剩下的两个链表中选。伪代码如下：
Node merge(Node node1,Node node2){
If(nod1.value<node2.value){
Phead = node1;
Phead.next = nerge(node1.next,node2);
}Else{
Phead = node2;
Phead.next = nerge(node1,node2.next);
}
}
（7）链表翻转
算法思路：从后往前插
```
linkListreverse(linkList head){
linkList p,q,pr;
p = head->next;
q =NULL;
head->next = NULL;
while(p){
pr = p->next;
p->next= q;
q = p;
p = pr;
}
head->next= q;
returnhead;
}
```
（8）两个链表的第一个公共节点
算法思路：1、借助栈；2、比较长度，然后快慢指针
（9）单链表的快排
struct Node {
int key;
Node* next;
Node(int nKey, Node* pNext) :
key(nKey) ,
next(pNext)
{}
};
[if !supportLists]10. [endif]
[if !supportLists]11. [endif]
[if !supportLists]12. [endif]Node* GetPartion(Node* pBegin, Node* pEnd)
[if !supportLists]13. [endif]{
[if !supportLists]14. [endif] int key = pBegin->key;
[if !supportLists]15. [endif] Node* p = pBegin;
[if !supportLists]16. [endif] Node* q = p->next;
[if !supportLists]17. [endif]
[if !supportLists]18. [endif] while(q != pEnd)
[if !supportLists]19. [endif] {
[if !supportLists]20. [endif] if(q->key < key)
[if !supportLists]21. [endif] {
[if !supportLists]22. [endif] p = p->next;
[if !supportLists]23. [endif] swap(p->key,q->key);
[if !supportLists]24. [endif] }
[if !supportLists]25. [endif]
[if !supportLists]26. [endif] q = q->next;
[if !supportLists]27. [endif] }
[if !supportLists]28. [endif] swap(p->key,pBegin->key);
[if !supportLists]29. [endif] return p;
[if !supportLists]30. [endif]}
[if !supportLists]31. [endif]
[if !supportLists]32. [endif]void QuickSort(Node* pBeign, Node* pEnd)
[if !supportLists]33. [endif]{
[if !supportLists]34. [endif] if(pBeign != pEnd)
[if !supportLists]35. [endif] {
[if !supportLists]36. [endif] Node* partion = GetPartion(pBeign,pEnd);
[if !supportLists]37. [endif] QuickSort(pBeign,partion);
[if !supportLists]38. [endif] QuickSort(partion->next,pEnd);
[if !supportLists]39. [endif] }
}
网友评论