void testReverse(void){

	printf("Testing reverse!\n");

	//reverse the list once...
	List l = setUpList();
	printList(l);
	reverseList(l);
	printList(l);


	assert(getElement(l, 0) == 4);
	assert(getElement(l, 1) == 7);
	assert(getElement(l, 2) == 8);
	assert(getElement(l, 3) == 1);
	assert(listLength(l) == START_LENGTH);

	//reverse it again!
	reverseList(l);
	printList(l);
	assert(getElement(l, 0) == 1);
	assert(getElement(l, 1) == 8);
	assert(getElement(l, 2) == 7);
	assert(getElement(l, 3) == 4);
	assert(listLength(l) == START_LENGTH);

	//testing that appended items are reversed as well
	append(l, 32);
	reverseList(l);
	assert(getElement(l, 0) == 32);
	assert(listLength(l) == START_LENGTH + 1);

	printf("Reversing passed!\n");
}

void testReverseList() {
    cout << endl;
    cout << "Test reverseList():" << endl;
    cout << "===================" << endl;

    char a[] = "a";
    char b[] = "b";
    char c[] = "c";
    char d[] = "d";
    char e[] = "e";
    char f[] = "f";
    char g[] = "g";

    Node<char*> head;
    head.data = a;
    head.next = nullptr;
    appendToList(&head, &b[0]);
    appendToList(&head, &c[0]);
    appendToList(&head, &d[0]);
    appendToList(&head, &e[0]);
    appendToList(&head, &f[0]);
    appendToList(&head, &g[0]);
    printList(&head);

    Node<char*>* rev = reverseList(&head);
    printList(rev);

    Node<char*>* orig = reverseList(rev);
    printList(orig);
}

int main(int argc, char **argv)
{
    int i;
    int n;
    NodePtr node;
    JobPtr job;
    ListPtr list;

    if (argc != 2) {
        fprintf(stderr, "Usage: %s <list size> \n",argv[0]);
        exit(1);
    }
    n = atoi(argv[1]);

    list = createList();
    for (i=0; i<n; i++) {
        job = createJob(i, "cmd args");
        node = createNode(job);
        addAtFront(list, node);
    }

    printList(list);
    reverseList(list);
    printList(list);
    reverseList(list);
    printList(list);

    exit(0);
}

    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (head == NULL)
            return NULL;

        if (head->next == NULL || m == n)
            return head;

        m--; n--;

        if (m == 0)
        {
            head = reverseList(head, n - m + 1);
            return head;
        }

        int c = 0;
        ListNode* curNode = head;
        ListNode* tail = NULL;
        while (c < m)
        {
            assert(curNode);
            tail = curNode;
            curNode = curNode->next;
            c++;            
        }

        curNode = reverseList(curNode, n - m + 1);
        tail->next = curNode;

        return head;
    }

    // O(n)-time, O(1)-space
    bool isPalindrome2(ListNode *head) {
        if (head == NULL) {
            return true;
        }

        // 计算中间节点
        ListNode *mid = findMiddleNode(head);

        // 反转后半段链表
        ListNode *reverseHead = reverseList(mid->next);

        // 连接前后两半段链表
        mid->next = reverseHead;

        // 比较前后两个半段链表
        // 注意：后半段链表节点个数 <= 前半段链表节点个数
        bool isPal = true;
        while (reverseHead != NULL) {
            if (head->val != reverseHead->val) {
                isPal = false;
            }
            head = head->next;
            reverseHead = reverseHead->next;
        }

        // 恢复原链表
        reverseHead = reverseList(mid->next);
        mid->next = reverseHead;

        return isPal;
    }

/* Deletes nodes which have a node with greater value node on left side */
void delLesserNodes(struct Node **head_ref)
{
	/* 1) Reverse the linked list */
	reverseList(head_ref);
  /*  2) In the reversed list, delete nodes which have a node with greater value node on left side. 
      Note that head node is never deleted because it is the leftmost node.*/
	_delLesserNodes(*head_ref);
  /* 3) Reverse the linked list again to retain the original order */
	reverseList(head_ref);
}

void linkedListTest() {
    node * list = nullptr;
    print(list);
    std::cout << "↔";
    reverseList(list);
    print(list);
    for (const auto & elem : {5,1,3,2,4,8,6,9,7}) {
        appendList(list, elem);
        print(list);
        std::cout << "↔";
        reverseList(list);
        print(list);
    }
}

 bool isPalindrome(ListNode* head) {
     if (head == nullptr || head->next == nullptr) return true;
     ListNode* slow = head;
     ListNode* fast = head;
     while (fast->next != nullptr && fast->next->next != nullptr) {
         fast = fast->next->next;
         slow = slow->next;
     }
     ListNode* right = reverseList(slow->next);
     slow->next = nullptr;
     bool result = compare(head, right);
     slow->next = reverseList(right);
     return result;
 }

void test( int* arr, int size ) {
  node* root = newList( arr, size );
  print( root );
  reverseList( &root );
  print( root );
  freeList( root );
}

    void reorderList(ListNode* head) {
        if (head==NULL || head->next==NULL || head->next->next==NULL)
        {
            return ;
        }
        
        ListNode* l1=head;
        ListNode* l2=getMid(head);
        ListNode* reverseL2=reverseList(l2);
        
		ListNode* newhead=new ListNode(-1);
        ListNode* tail=newhead;
        while (l1!=NULL && reverseL2!=NULL)
        {
			tail->next=l1;
            l1=l1->next;
			tail=tail->next;
            tail->next=reverseL2;
			tail=tail->next;
            reverseL2=reverseL2->next;
        }
       if (l1!=NULL)
       {
		   tail->next=l1;
       }
	   if (reverseL2!=NULL)
	   {
		   tail->next=reverseL2;
	   }
	   head=newhead->next;
    }

int main() {
    struct node * head   = NULL;
    struct node * second = NULL;
    struct node * third  = NULL;

    head   = (struct node *) malloc(sizeof(struct node));
    second = (struct node *) malloc(sizeof(struct node));
    third  = (struct node *) malloc(sizeof(struct node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    printf("Normal list order:\n");
    printList(head);
    printf("\nReversed order:\n");
    reverseList(&head);
    printList(head);

    return 0;
}

 ListNode* reverseList(ListNode* head) {
     if (!head || !(head->next)) return head;
     ListNode* tmp = reverseList(head->next);
     head->next->next = head;
     head->next = NULL;
     return tmp;
 }

 ListNode* reverseList(ListNode *head, int k) {
     ListNode *prev, *current, *next, *tail;
     current = head, prev = NULL, tail = head;
     int cnt = 0;
     while (current != NULL) {
         if (cnt > k)
             break;
         current = current->next;
         cnt++;
     }
     if (cnt < k)
         return head;
     cnt = 0;
     current = head;
     while (cnt < k && current != NULL) {
         next = current->next;
         current->next = prev;
         prev = current;
         current = next;
         cnt++;
     }
     if (current != NULL)
         tail->next = reverseList(current, k);
     return prev;
     
 }

int main()
{
    node *listHead = create();
    if (!listHead)
        return 0;
    for (int i = 0; i < 10; i++)
        add(listHead, i);
    deleteNode(listHead, 5);
    insertNode(listHead, 5, 50);

    printf("Length = %d\n", length(listHead));
    printList(listHead);
    reverseList(listHead);
    printList(listHead);

    node *pMid;
    pMid = getMid(listHead);
    printf("Mid data is %d\n", pMid->data);
    add(listHead, 99);
    printList(listHead);
    pMid = getMid(listHead);
    printf("Mid data is %d\n", pMid->data);

    destroy(listHead);
    return 0;
}

 ListNode* reverseList(ListNode* head){
     if(!head || !head->next) return head;
     ListNode* newHead = reverseList(head->next);
     head->next->next = head;
     head->next = NULL;
     return newHead ;
 }

 ListNode *reverseKGroup(ListNode *head, int k) {
     /* https://oj.leetcode.com/problems/reverse-nodes-in-k-group/
     e.g.,
     Given this linked list: 1->2->3->4->5
     For k = 2, you should return: 2->1->4->3->5
     For k = 3, you should return: 3->2->1->4->5
     */
     
     if (head == NULL || head->next == NULL || k < 2) return head;
     
     ListNode *dummy = new ListNode(0), *tail = dummy;
     
     while (head != NULL) {
         ListNode *tmp = head;
         for (int i = 1; i < k && tmp != NULL; i++) {
             tmp = tmp->next;
         }
         if (tmp == NULL) {
             tail->next = head;
             break;
         }
         
         ListNode *tmp2 = tmp->next;
         tmp->next = NULL;
         reverseList(head);
         tail->next = tmp;
         tail = head;
         head = tmp2;
     }
     
     head = dummy->next;
     delete dummy;
     return head;
 }

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* node = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return node;
}

int main(void)
{
    int i = 0, ret = 0;
    struct node *ptr = NULL;

    print_list();

    for(i = 0; i<100000000; i++)
        add_to_list(i);
    
	//print_list();

	ptr = search_in_list(99999999, NULL);
	if(NULL == ptr)
	{
    	printf("Search [val = %d] failed, no such element found\n",i);
    }
    else
    {
        printf("Search passed [val = %d]\n",ptr->val);
    }

    printf("Lets reverse the linked list\n");

    reverseList();

    return 0;
}

 ListNode *reverseBetween(ListNode *head, int m, int n) {
     ListNode *list = head;
     if (m != n) {
         ListNode *pm = NULL, *prem = NULL, *pn = NULL, *nextn = NULL;
         int index = 1;
         ListNode *p = head, *pre = NULL;
         // 找到m、n两个结点
         while (index <= n && p != NULL) {
             if (index == m) {
                 prem = pre;
                 pm = p;
             }
             if (index == n) {
                 pn = p;
                 nextn = p->next;
             }
             index++;
             pre = p;
             p = p->next;
         }
         // 倒序链表 m --> ... -> n
         pn->next = NULL;
         ListNode *from, *to;
         reverseList(pm, &from, &to);
         // 加上头尾
         to->next = nextn;
         if (prem == NULL) {
             list = from;
         } else {
             prem->next = from;
         }
     }
     return list;
 }

int main()
{
    struct ListNode *p1,*p2,*head;
    for(int i=0;i<2;i++)
    {
        if(i ==0)
        {
            p1=(struct ListNode *)malloc(sizeof(struct ListNode));
            p1->val=i;
            p1->next=NULL;
            head=p1;
        }
        else
        {
            p2=(struct ListNode *)malloc(sizeof(struct ListNode));
            p2->val=i;
            p2->next=NULL;
            p1->next=p2;
            p1=p1->next;
        }
    }
    printf("origin:");
    printlist(head);
    p2=reverseList(head);
    printf("after:");
    printlist(p2);
}