# 考研算法题

typedef sturct ListNode{
int data;
struct ListNode *next;
}ListNode;

struct ListNode *pre = NULL, *cur = head, *t;
while(cur){
t = cur -> next;    //暂存后继节点
cur -> next = pre;  //修改引用指针
pre = cur;  //暂存当前节点
cur = t;    //访问下一节点
}
return pre;
}


 ListNode* reverseList(ListNode* head) {
}

ListNode* dfs(ListNode *cur, ListNode *pre){
if(cur == NULL) return pre; //递归终止条件
ListNode* t = dfs(cur -> next, cur);    //递归后继节点
cur -> next = pre;  //修改节点指向
return t;   //返回反转链表头节点
}


ListNode* removeNthFromEnd(ListNode* head, int n) {
while(p != NULL){
if(n < 0)   q = q -> next;
n --;
p = p -> next;
}
if(n == 0)  return head -> next;
q -> next = q -> next -> next;
}


int removeDuplicates(vector<int>& nums) {
if(nums.size() == 0)    return 0;
int len = 1;
int l = 0, r = 1;
while(r < nums.size()){
while(nums[l] != nums[r] && r < nums.size()){
nums[++ l] = nums[r];
r ++;
len ++;
if(r == nums.size())    break;
}
r ++;
}
return len;
}


bool isValidBST(TreeNode* root) {
return dfs(root, LONG_MIN, LONG_MAX);
}

bool dfs(TreeNode* root, long mi, long mx){
if(root == NULL)    return true;
if(root->val <= mi || root->val >= mx)    return false;
return dfs(root -> left, mi, root->val) && dfs(root -> right, root->val, mx);
}


vector<int> searchRange(vector<int>& nums, int target) {
vector<int> ans;
int n = nums.size();
if(n == 0){
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
int l = 0, r = n - 1;
while(l < r){
int mid = (l + r) >> 1;
if(nums[mid] >= target)    r = mid;
else   l = mid + 1;
}
if(nums[r] != target){
ans.push_back(-1);
ans.push_back(-1);
return ans;
}
else{
ans.push_back(r);
l = 0, r = n - 1;
while(l < r){
int mid = (l + r + 1) >> 1;
if(nums[mid] <= target)    l = mid;
else   r = mid - 1;
}
ans.push_back(l);
return ans;
}
}


 int dfs(TreeNode *root){
if(root == NULL)    return 0;
int left = dfs(root -> left);
int right = dfs(root -> right);
if(left != -1 && right != -1 && abs(left - right) < 2){
return left > right ? left + 1 : right + 1;
}
else{
return -1;
}
}

bool isBalanced(TreeNode* root) {
int ans = dfs(root);
return ans == -1 ? false : true;
}


 bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == NULL && q == NULL)  return true;
else if(p == NULL || q == NULL) return false;
else if(p -> val != q -> val)  return false;
else{
return isSameTree(p -> left, q -> left) && isSameTree(p -> right, q -> right);
}
}


typedef struct BTNode{
int data;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;

int Get_K_Level_Number(BTNode *root, int k){
if(root == NULL || k == 0)  return 0;
if(k == 1)  return 1;
return Get_K_Level_Number(root -> lchild, k + 1) + Get_K_Level_Number(root -> rchild, k + 1);
}


typedef struct TreeNode{
int data;
struct TreeNode *lchild;
struct TreeNode *rchild;
struct TreeNode *parent;
}TreeNode;

TreeNode* GetNext(TreeNode* node){
if(node == NULL){
return NULL;
}
//如果当前节点有右子树,找右子树的最左节点
TreeNode* Pnext = NULL:
if(node -> rchild != NULL){
Pnext = node -> rchild;
while(Pnext -> lchild != NULL){
Pnext = Pnext -> lchild;
}
return Pnext;
}

//没有右子树，往上找某结点A，A是其父节点B的左节点，父节点B则是下一个节点
else{
TreeNode Prenode = node -> parent;
while(Prenode != NULL && node == Prenode -> rchild){
node = Prenode;
Prenode = node -> parent;
}
return Prenode;
}
}


int minDepth(TreeNode* root) {
if(root == NULL)    return 0;
if(root -> left == NULL && root -> right == NULL)   return 1;
int mi = INT_MAX;
if(root -> left != NULL)    mi = min(mi, minDepth(root -> left));
if(root -> right != NULL)   mi = min(mi, minDepth(root -> right));
return mi + 1;
}


    int res;
int kthLargest(TreeNode* root, int k) {
dfs(root, k);
return res;
}
void dfs(TreeNode* root, int &k){
if(root == NULL)    return;
dfs(root -> right, k);
k --;
if(k == 0){
res = root -> val;
return;
}
dfs(root -> left, k);
}


ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL || l2 == NULL)    return l1 ? l1 : l2;
if(l1 -> val < l2 -> val){
l1 -> next = mergeTwoLists(l1 -> next, l2);
return l1;
}
else{
l2 -> next = mergeTwoLists(l1, l2 -> next);
return l2;
}
}


typedef struct ArcNode{
struct ArcNode *next;
}ArcNode;

typdef struct VNode{
int data;
ArcNode *firstarc;
}VNode;

typedef struct AGraph{
VNode VList[maxn];
int n;
int e;
}AGraph;

int flag = 0;
int vis[maxn];

void dfs(AGraph G, int i, int j, int vis[]){
ArcNode *p;
vis[i] = 1;
if(i == j){
found = 1;
return ;
}
else{
p = G.VList[i].firstarc;
whlie(flag == 0 && p != NULL){
dfs(G, p -> adjex, j, vis);
}
p = p -> next;
}
}
}

int FindPath(AGraph G, int i, int j){
for(int i = 0; i < G.n; i ++){
vis[i] = 0;
}
if(i == j)  return 0;
dfs(G, i, j, vis);
return flag;
}


DFS判断有向图是否存在环

const int maxn = 1000;

typedef struct ArcNode{
struct ArcNode *next;
}ArcNode;

typdef struct VNode{
int data;
ArcNode *firstarc;
}VNode;

typedef struct AGraph{
VNode VList[maxn];
int n;
int e;
}AGraph;

int flag = 0;
int vis[maxn];

void dfs(AGraph G, int i){
ArcNode *p;
vis[i] = 1;//1 表示正在访问
p = G.VList[i].firstarc;
while(p != NULL){
}
else if(vis[p -> adjex] == 1){//访问到标记节点，说明有环
flag = 1;
}
p = p -> next;
}
vis[i] = 3;//3 表示该点访问结束
}

bool Has_Circle(AGraph G){
for(int i = 0; i < G.n; i ++){
vis[i] = 0;
}
for(int i = 0; i < G.n; i ++){
if(vis[i] == 0){
dfs(G, i);
}
}
return flag ? true : false;
}


int climbStairs(int n) {
int c = 0, a = 0, b = 1;
for(int i = 1; i <= n; i ++){
c = a + b;
a = b;
b = c;
}
return c;
}