#define _CRT_SECURE_NO_WARNINGS 1



////c语言栈的判断成对的括号
//typedef char Stdatatype;
//
//typedef struct stack
//{
//	Stdatatype* arr;
//	int top;
//	int capacity;
//}ST;
//
////初始化
//void StackInit(ST* ps);
//
////入栈
//void StackPush(ST* ps, Stdatatype x);
//
////出栈
//void StackPop(ST* ps);
//
////判空
//bool StackEmpty(ST* ps);
//
////判断栈元素
//Stdatatype Stacktop(ST* ps);
//
////栈销毁
//void StackDestroy(ST* ps);
//
////栈大小
//int StackSize(ST* ps);
//
////初始化
//void StackInit(ST* ps)
//{
//	assert(ps);
//
//	Stdatatype* temp = (Stdatatype*)malloc(0 * sizeof(Stdatatype));
//	if (temp == NULL)
//	{
//		printf("Init:fail\n");
//		return;
//	}
//	ps->arr = temp;
//	ps->capacity = 0;
//	ps->top = 0;//top定义为0的话那么就对应输入值的下一位，即先输入再++，，若是-1为初始化，就是先++再输入
//}
//
////入栈
//void StackPush(ST* ps, Stdatatype x)
//{
//	assert(ps);
//
//	if (ps->capacity == ps->top)
//	{
//		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//		Stdatatype* temp = (Stdatatype*)realloc(ps->arr, newcapacity * sizeof(Stdatatype));
//		if (!temp)
//		{
//			printf("realloc:fail\n");
//			exit(-1);//错误就无法进行了，直接退出
//		}
//		ps->capacity = newcapacity;
//		ps->arr = temp;
//	}
//
//	ps->arr[ps->top] = x;
//	ps->top++;
//
//}
//
////出栈
//void StackPop(ST* ps)
//{
//	assert(ps);
//	assert(ps->top > 0);//等于0就说明没有数据了。不能删了
//
//	ps->top--;
//
//}
//
////判空
//bool StackEmpty(ST* ps)
//{
//	assert(ps);
//
//	//无需三目或者条件
//	//直接返回
//	return ps->top == 0;
//}
//
////判断栈顶元素
//Stdatatype Stacktop(ST* ps)
//{
//	assert(ps);
//	assert(ps->top > 0);
//	return ps->arr[ps->top - 1];
//}
//
////栈销毁
//void StackDestroy(ST* ps)
//{
//	assert(ps);
//	free(ps->arr);
//	ps->capacity = 0;
//	ps->top = 0;
//	free(ps);
//}
//
//int StackSize(ST* ps)
//{
//	assert(ps);
//	return ps->top;
//}
//bool isValid(char* s) {
//
//	assert(s);
//	ST ps = { 0 };
//	StackInit(&ps);
//
//	while (*s)
//	{
//		if ((*s == '(') || (*s == '{') || (*s == '['))
//		{
//			StackPush(&ps, *s);
//			s++;
//		}
//		else
//		{
//			if (StackEmpty(&ps))                  //如果再这为空说明该开始就是错的
//				return false;
//			char top = Stacktop(&ps);//*s只包含括号，所以只需要考虑括号的比就行
//			StackPop(&ps);
//			if ((*s == ']' && top != '[') || (*s == '}' && top != '{') || (*s == ')' && top != '('))
//				return false;
//			else
//			{
//				s++;
//			}
//		}
//
//	}
//
//	if (StackEmpty(&ps))
//		return  true;
//	return false;
//
//}


////归并有序链表
//struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
//    if (!l1)             //其中一个为空直接返回
//        return l2;
//    else if (!l2)
//        return l1;
//
//    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
//    struct ListNode* tail = head;
//    while (l1 && l2)//其中一个结尾就结束
//    {
//        if (l1->val > l2->val)
//        {
//            //接l2
//            tail->next = l2;
//            l2 = l2->next;
//
//            tail = tail->next;
//            tail->next = NULL;
//        }
//        else
//        {
//            //接L1
//            tail->next = l1;
//            l1 = l1->next;
//
//            tail = tail->next;
//            tail->next = NULL;
//        }
//    }
//    //一边结束接另一边，只有可能一边为空一边不为空
//    if (l1)
//        tail->next = l1;
//    if (l2)
//        tail->next = l2;
//    return head->next;
//}



////反转链表
//struct ListNode* reverseList(struct ListNode* head) {
//    //取出第一个头插在目标新链表中
    //struct ListNode* newhead = NULL;
    //struct ListNode* cur = head;
    //while (cur)
    //{
    //    struct ListNode* next = cur->next;
    //    cur->next = newhead;
    //    //更新newhead
    //    newhead = cur;
    //    cur = next;
    //}
    //return newhead;
//}

////递归判断回文
// //    //1.找到中间节点，然后反转之后的链表，然后再对比链表即可
//    //2.利用数组，快速对比
//    //3.建立一个全局变量，利用递归找到最后一个元素，然后对打比全局变量首个元素
// 
// 
//struct ListNode* firstpoints;
//
//bool remo(struct ListNode* current)
//{
//    if (current != NULL)
//    {
//        if (!remo(current->next))
//            return false;       //找到最后一个，最后一个为空就是true之后再判断
//        if (current->val == firstpoints->val)
//            firstpoints = firstpoints->next;//相等移动前面指针，末尾指针会随着递归收回来
//        else
//            return false;//不相同就会直接返回false，递归第一个条件就会一直返回false
//    }
//    return true;
//}
//
//bool isPalindrome(struct ListNode* head) {

//    firstpoints = head;
//    return remo(head);
//}