链表

链表问题通常可以在链表头部加入一个哑节点来减少讨论的情况。

1，翻转链表

递归

Node * reverseList(List head)
{
    if(head == NULL || head->next == NULL)
        return head;

    else
    {
        Node *newhead = reverseList(head->next);
        head->next->next = head; 
        //翻转后最后一个节点是原来的head->next,再把head放在它后面
        head->next = NULL;  //链尾置空
        
        return newhead;
    }
}

非递归

    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;
        
        ListNode* newhead = new ListNode(0);//构造一个哑头部节点
        ListNode*p=head,*q=head;
        //头插法，p遍历每个节点，q存储p的下一位置
        while(p){
            q=p->next;
            p->next=newhead->next;
            newhead->next=p;
            p=q;
        }
        return newhead->next;
    }

2，一个链表是否有环，环入口

node* first_loop_port(node *head)  
{  
    node *slow = head, *fast = head;  
  
    while ( fast && fast->next )   
    {  
        slow = slow->next;  
        fast = fast->next->next;  
        if ( slow == fast ) break;  
    }  
  
    if (fast == NULL || fast->next == NULL)  //否则有环
        return NULL;  
  
    slow = head;  
    while (slow != fast)  
    {  
         slow = slow->next;  
         fast = fast->next;  
    }  
  
    return slow;  
} 

求环的入口，从相遇点和起点各发出一个速度为一步的指针，两个指针再次相遇的地方就是环的入口。（证明比较麻烦）
或者，得出相遇点后，从该点绕一圈，得到环的长度。然后从起点发出两个指针，两指针距离差为环的距离，当两个指针相遇时就是环的入口。

3，两个链表是否相交，相交点

先判断两个两链表是否有环
1）若都无环，p1=0,p2=len2-len1,p1++,p2++,看是否相遇
2）若一个有环，一个没有，则不相交
3）若都有环，判断环1的相遇点是否在环2上

4，链表排序

归并排序

    ListNode* sortList(ListNode* head) {
        if(!head || !head->next) return head;
        
        ListNode* k=head,*m=head;//快慢指针找中点
        while(k->next && k->next->next){
            m=m->next;
            k=k->next->next;
        }

        ListNode *L1=head,*L2=m->next;
        m->next=NULL;
        L1=sortList(L1); //递归左右，再合并
        L2=sortList(L2);
        ListNode* newhead=merge(L1,L2);
        return newhead;
    }

    ListNode* merge(ListNode* L1, ListNode* L2){
        if(!L1) return L2;
        if(!L2) return L1;

        ListNode* prehead=new ListNode(0);
        ListNode* tail=prehead,*p1=L1,*p2=L2;
        while(p1 && p2){
            if(p1->val < p2->val){
                tail->next=p1;
                tail=tail->next;
                p1=p1->next;
            }
            else{
                tail->next=p2;
                tail=tail->next;
                p2=p2->next;
            }
        }
        if(p1)
            tail->next=p1;
        else
            tail->next=p2;

        ListNode* head=prehead->next;
        delete prehead;
        return head;
    }

快速排序
和数组的快速排序区别在于：
1，以首元素为枢纽
2，区间是左闭右开

    //调用: sortList(head,NULL)
    ListNode* sortList(ListNode* head,ListNode* end){ 
        if(head!=end){  //[)区间
            ListNode* pivot=partition(head,end);
            sortList(head,pivot);
            sortList(pivot->next,end);
        }
        return head;
    }

    ListNode* partition(ListNode* head,ListNode* end){
        ListNode *p=head,*q=head;
        while(q!=end){
            if(q->val < head->val){  //以节点为枢纽
                p=p->next;   //p是小与枢纽元素的最后一个位置
                swap(p->val,q->val);
            }
            q=q->next;
        }
        swap(p->val,head->val);  //此时p指向枢纽元素
        return p;
    }