[数据结构与算法]leetcode

链表

反转链表

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        ListNode *pre = nullptr,*cur = pHead,*nex = nullptr;
        while(cur != nullptr) {
            nex = cur -> next;
            cur -> next = pre;
            pre = cur;
            cur = nex;
        }
        return pre;
    }
};

判断链表是否有环

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
       unordered_map<ListNode*, bool>mp;
       ListNode *x = head;
       while(x && mp.find(x) == mp.end()) {
           mp[x] = 1;
           x = x -> next;
       }
       if(x == nullptr) return 0;
       return 1;
    }
};

重排链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        if(!head) return;
        deque<ListNode *>q;
        while(head){q.push_back(head); head = head->next;}
        ListNode *x = nullptr; bool isFirst = 1;
        while(!q.empty()) {
            if(isFirst) {
                x = q.front();
                q.pop_front();
                isFirst = 0;
            }
            else if(!q.empty()) {
                x -> next = q.front();
                q.pop_front();
                x = x->next;
            }
            if(!q.empty()) {
                x -> next = q.back();
                q.pop_back();
                x = x->next;
            }
        }
        x -> next = nullptr;
    }
};

排序

从小到大排序

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    int a[(int)(1e6) + 10],b[(int)(1e6) + 10];
    void qsort(int L,int R) {
        if(L>=R) return ;
        int mid = (L+R)>>1;
        qsort(L,mid); qsort(mid+1,R);
        int x = L; int y = mid+1; int t = x;
        while(x<=mid && y<=R) {
           if(a[x] <= a[y]) b[t++] = a[x],x++;
            else b[t++] = a[y],y++;
        }
        while(x<=mid) b[t++] = a[x],x++;
        while(y<=R) b[t++] = a[y],y++;
        for(int i=L;i<=R;i++) a[i] = b[i];
    }
    vector<int> MySort(vector<int>& arr) {
        // write code here
        for(int i=0;i<(int)(arr.size());i++) a[i] = arr[i];
        qsort(0,arr.size()-1);
        for(int i=0;i<(int)(arr.size());i++) arr[i] = a[i];
        return arr;
    }
};

寻找第K大

class Solution {
public:
    int A[1000010];
    int B[1000010];
    int qsort(int L,int R,int k) {
        int pilot = A[L]; L++;
        int i = L; int j = R;
        for(int p=L;p<=R;p++) {
            if(A[p] <= pilot) B[j--] = A[p];
            else B[i++] = A[p];
        }
        for(int p=L;p<=R;p++) A[p] = B[p];
        if(i-L+1 == k) return pilot;
        else if(i-L+1 < k) {
            return qsort(i,R,k - (i-L+1));
        }else {
            return qsort(L,j,k);
        }
    }
    int findKth(vector<int> a, int n, int K) {
       for(int i=0;i<n;i++) A[i] = a[i];
       return qsort(0,n-1,K);
    }
};