一、线性表

0x00 二分法

查找>=key的第一个元素，描述为满足某种情况的最小的元素。

如 2 3 3 4 4 4 5查找 4 则返回 下标3 即最左边的4

    int l = 0, r = n-1;
        while(l < r){
            int mid = l + r >> 1;
            if(a[mid] >= x) r = mid;
            else l = mid+1;
        }
        if(a[l]!=x) printf("-1 -1\n");//查找失败
查找小于<=key的最后一个元素，描述为满足某种情况的最大的元素。

如 2 3 3 4 4 4 5查找 4 则返回 下标5 即最右边的4

        int l = 0, r = n-1;
            while(l < r){
                int mid = l+r+1>>1;
                if(a[mid] <= x) l = mid;
                else r = mid-1;
            }
            if(a[l]!=x) printf("-1 -1\n");//查找失败
0x01 回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2 输出: false

示例 2:

输入: 1->2->2->1 输出: true

    //     s-慢指针 f-快指针
        //     循环结束时的状态如下:
        //     1 2 2 1 NULL 偶数长度 后半部分起点就是s
        //         s    f
        // else
        //     1 2 3 2 1 奇数长度  后半部分起点是s的下一个
        //         s   f
    bool isPalindrome(ListNode* head) {
        if(!head||!head->next) return true;//0个或1个数自然为真
        stack<int> stk;//存放前半个数
        auto f = head,s = head;
        while(f&&f->next){
            stk.push(s->val);
            s = s->next;
            f = f->next->next;
        }
        if(f) s = s->next;//后半部分起点
        while(s){
            if(s->val!=stk.top()) return false;
            stk.pop(),s = s->next;
        }
        return true;
    }
0x02 删除链表的倒数第n个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *L = new ListNode(0);
        L->next = head;
        ListNode *f = L,*s = L;
        while(n--&&f->next){f = f->next;}
        while(f->next){
            s = s->next;
            f = f->next;
        }
        s->next = s->next->next;
        return L->next;
    }
0x03 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4, 1->3->4

输出：1->1->2->3->4->4

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//迭代版
        auto h = new ListNode(0), r = h;//r为尾结点
        while(l1&&l2){
            if(l1->val < l2->val) r->next = l1,l1 = l1->next,r = r->next;//把l1连到尾部
            else r->next = l2,l2 = l2->next,r = r->next;
        }
        if(!l1) r->next = l2; 
        if(!l2) r->next = l1;
        return h->next;
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//递归版
        if(!l1) return l2;//空时
        if(!l2) return l1;
        if(l1->val < l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } 
        else{
            l2->next = mergeTwoLists(l1,l2->next);
            return l2;
        } 
    }
0x04 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

解释:

向右旋转 1 步: 5->1->2->3->4->NULL

向右旋转 2 步: 4->5->1->2->3->NULL

   ListNode* rotateRight(ListNode* head, int k) {
        if(!head) return head;
        auto f = head, s = head;
        int n = 0;
        while(f){n++,f = f->next;}
        k = k%n;
        f = head;
        while(k-- && f->next) f = f->next;
        while(f->next) s = s->next, f = f->next;
        f->next = head;
        head = s->next;
        s->next = NULL;
        return head;
    }
0x05 反转链表

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(m==n) return head;
        auto L = new ListNode(0);
        L->next = head;
        auto a = L,d = L->next;
        for(int len = n-m;len > 0;len--) d = d->next;
        while(m-->1){
            a = a->next;
            d = d->next;
        }
        auto c = a->next, b = d->next;
        for(auto p = c, q = c->next; q!=b;){
            auto r = q->next;
            q->next = p;
            p = q;
            q = r;
        }
        a->next = d;
        c->next = b;
        return L->next;

    }
0x06 有序链表转换二叉搜索树

给定一个单链表，其中的元素按升序排序，转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    vector<int> vec;
    int mid;
    TreeNode* sortedListToBST(ListNode* head) { 
        vec.clear();
        while(head){
            vec.push_back(head->val);
            head=head->next;
        }
       return buildTree(0,vec.size()-1);  
    }
    TreeNode*buildTree(int l,int r){
       if(l>r) return NULL;
       int mid=(l+r)/2;
       TreeNode *p=new TreeNode(vec[mid]);
       p->left=buildTree(l,mid-1);
       p->right=buildTree(mid+1,r);
       return p;
     }
0x07 环形链表

给定一个链表，返回链表开始入环的第一个节点.如果链表无环，则返回 null。

   ListNode *detectCycle(ListNode *head) {
        ListNode *slow=head,*fast=head;
        while(fast){
            slow = slow->next;
            fast = fast->next;
            if(fast) fast =  fast->next;
            else break;
            if(slow==fast){
                slow = head;
                while(slow!=fast){
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }
0x08 链表的插入排序

输入: 4->2->1->3

输出: 1->2->3->4

    ListNode* insertionSortList(ListNode* head) {
        auto h = new ListNode(-1),pre = h,q=head;
        for(auto p = head; p; p=q){//把head的每个节点p插入到h链中
            for(pre = h; pre->next&&p->val>pre->next->val;pre = pre->next){}//找插入点
            q = p->next,p->next = pre->next, pre->next = p;//插入
        }
        return h->next;
    }
0x09 链表的归并排序

    ListNode *sortList(ListNode *head){
        if (!head || !head->next) return head;
        ListNode *s = head, *f = head->next;
        //找到链表的中间位置
        while (f&&f->next){        //快慢指针，注意必须前两步存在
            s = s->next;
            f = f->next->next;
        }
        ListNode *l1 = sortList(s->next);        //右链表
        s->next = NULL;        //将其断开，为两个链表
        ListNode *l2 = sortList(head);
        return merge(l1, l2);
    }
    ListNode *merge(ListNode *l1, ListNode *l2){
        auto h = new ListNode(0), r = h;//r为尾结点
        while(l1&&l2){
            if(l1->val < l2->val) r->next = l1,l1 = l1->next,r = r->next;//把l1连到尾部
            else r->next = l2,l2 = l2->next,r = r->next;
        }
        if(!l1) r->next = l2; 
        if(!l2) r->next = l1;
        return h->next;
    }
0x0a 多项式加法和乘法

#include<bits/stdc++.h>
using namespace std;
typedef struct ListNode{
    int val,ex;//系数和指数
    ListNode *next;
    ListNode(int v, int e) : val(v),ex(e),next(NULL){ }
};
void display(ListNode *h){
    ListNode *p = h->next;
    if(!p){
        printf("0 0");//零多项式
        return;
    }
    else printf("%d %d",p->val,p->ex),p = p->next;//第一项单独输出
    while(p) printf(" %d %d",p->val,p->ex),p = p->next;
}
ListNode* add(ListNode *h1, ListNode *h2){
    ListNode *h = new ListNode(-1,-1), *r = h,*p = h1->next,*q = h2->next;
    while(p&&q){
        if(p->ex > q->ex) r->next = new ListNode(p->val,p->ex),r = r->next, p = p->next;
        else if(p->ex < q->ex) r->next = new ListNode(q->val,q->ex),r = r->next, q = q->next;
        else{
            if(q->val+p->val==0){//抵消时
                p = p->next,q = q->next;
                continue;
            } 
            r->next = new ListNode(q->val+p->val,q->ex);
            r = r->next, p = p->next,q = q->next;
        } 
    }
    if(!p) r->next = q;
    if(!q) r->next = p;
    return h;
}
ListNode* mult(ListNode *h1, ListNode *h2){
    ListNode *h = new ListNode(-1,-1);
    for(ListNode *p = h1->next; p; p = p->next){
        for(ListNode *q = h2->next; q; q = q->next){
            int val = p->val*q->val, ex = p->ex+q->ex;//一项乘积的值
            ListNode *pre = h;
            for(; pre->next&&pre->next->ex > ex; pre = pre->next){};//找到插入位置
            if(pre->next&&pre->next->ex==ex){
                pre->next->val += val;//指数相同,合并同类项
                if(pre->next->val==0){//合并后系数为零，则需要删除
                    ListNode *t = pre->next;
                    pre->next = pre->next->next;
                    delete t;
                }
            } 
            else {
                ListNode *d = new ListNode(val,ex);//乘积项节点 待插入
                d->next = pre->next, pre->next = d;
            }
        }
    }
    return h;
}
int main(){
    ListNode *h1 = new ListNode(-1,-1), *h2 = new ListNode(-1,-1), *r1 = h1, *r2 = h2;//建立两个表达式的头结点
    int n, m, v, e;
    scanf("%d",&n);
    while(n--){//尾插法建立表达式链表
        scanf("%d %d",&v,&e);
        r1->next = new ListNode(v,e);
        r1 = r1->next;
    }
    scanf("%d",&m);
    while(m--){
        scanf("%d %d",&v,&e);
        r2->next = new ListNode(v,e);
        r2 = r2->next;
    }
    display(mult(h1,h2));
    printf("\n");
    display(add(h1,h2));
    return 0;
}
0x0b 相交链表

找到两个单链表的交点

A和B两个链表长度可能不同，但是A+B和B+A的长度是相同的，所以遍历A+B和遍历B+A一定是同时结束。如果相交的话，A和B有一段尾巴是相同的，所以两个指针一定会同时到达交点。

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto pa = headA,pb = headB;
        while(pa!=pb){
            pa = (pa ? pa->next:headB);
            pb = (pb ? pb->next:headA);
        }
        return pa;
    }
0x0c 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

输入: 1->1->2->3->3

输出: 1->2->3

    ListNode* deleteDuplicates(ListNode* head) {
        auto f = head;
        while(f){
            if(f->next&&f->val==f->next->val) f->next = f->next->next;
            else f = f->next;
        }
        return head;
    }
0x0d 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

输入: 1->2->3->3->4->4->5

输出: 1->2->5

    ListNode* deleteDuplicates(ListNode* head) {
        auto h = new ListNode(-1);//添加头结点
        h->next = head;
        auto pre = h,p = pre->next;//pre指向无重复的最后一个数 p为遍历节点
        while(p){
            while(p->next&&p->val==p->next->val) p = p->next;//p与后不同时退出
            if(pre->next==p) pre = p, p = p->next;//表示p是无重复元素，更新无重复数 pre = p 
            else p = p->next,pre->next = p;//p是重复元素,[pre->next,p]全重复 跳过这段即可
        }
        return h->next;
    }