（7）列表相关题目

（1）从头到尾打印链表
算法思路：1、递归；2、借助栈；
代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/List/PrintDes.java
（2）O(1)时间内删除链表节点
算法思路：1、从头开始遍历，找到待删除节点的前一个节点，然后接到待删除节点的下一个节点。但是时间复杂度是O(n);2、找到待删除节点的下一个节点，把它复制给待删除节点，并删除自己。
（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）链表翻转
算法思路：从后往前插。

linkList reverse(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;
  return head;
}

（8）两个链表的第一个公共节点
算法思路：1、借助栈；2、比较长度，然后快慢指针。
（9）单链表的快排

struct Node   {  
        int key;  
        Node* next;  
        Node(int nKey, Node* pNext)  
            : key(nKey)  
            , next(pNext)  
        {}  
    };        
Node* GetPartion(Node* pBegin, Node* pEnd)  {  
        int key = pBegin->key;  
        Node* p = pBegin;  
        Node* q = p->next;        
        while(q != pEnd){  
            if(q->key < key){  
                p = p->next;  
                swap(p->key,q->key);  
            }     
            q = q->next;  
        }  
        swap(p->key,pBegin->key);  
        return p;  
    }     
void QuickSort(Node* pBeign, Node* pEnd)  {  
        if(pBeign != pEnd)          {  
            Node* partion = GetPartion(pBeign,pEnd);  
            QuickSort(pBeign,partion);  
            QuickSort(partion->next,pEnd);  
        }  
    }  

（10）判断两个链表是否相交
算法思路：两个链表相交，尾节点必然相等
（11）两个链表相加
例如：（2->4->3）+(5->6->4) = (7->0->8)
算法思路：先将链表翻转，再挨个相加，同时看是否进位
代码见：https://github.com/yuanfuqiang456/LeetCode/blob/master/src/List/AddList.java