Reverse a LinkedList

/*
 * ListNode.cpp
 *
 *  Created on: Oct 4, 2013
 *      Author: roysong
 */


#include


#include "gtest/gtest.h"


typedef struct ListNode_ {
     struct ListNode_ *next;
     int value;
}ListNode;




ListNode* createNode(int value = 0) {
     ListNode *node = new ListNode;
     if (node != NULL) {
          node->value = value;
          node->next = NULL;
     }


     return node;
}


void destroyListNode(ListNode *head) {
     while (head != NULL) {
          ListNode *temp = head->next;
          delete head;
          head = temp;
     }
}




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


     ListNode *current = head->next;
     head->next = NULL;


     do {
          ListNode *next = current->next; // save next pointer
          current->next = head;           // reverse
          head = current;                 // move current pointer to head
          current = next;                 // move head to next element
     }while (current != NULL);


     return head;
}


TEST(ListNode, reverseNull) {
     ListNode *p = NULL;


     EXPECT_EQ(NULL, reverse(p));
}


TEST(ListNode, reverseOneElement) {
     ListNode* head = createNode(1);


     head = reverse(head);
     EXPECT_EQ(1, head->value) << "failure message";
     EXPECT_EQ(NULL, head->next);


     destroyListNode(head);
}


TEST(ListNode, reverseMultiElementes) {
     ListNode* list = createNode(1);
     ListNode* second = createNode(2);
     list->next = second;
     ListNode* third = createNode(3);
     second->next = third;


     ListNode *p = list;
     EXPECT_EQ(1, p->value);
     p = p->next;
     EXPECT_EQ(2, p->value);
     p = p->next;
     EXPECT_EQ(3, p->value);
     EXPECT_EQ(NULL, p->next);


     list = reverse(list);
     p = list;
     EXPECT_EQ(3, p->value);
     p = p->next;
     EXPECT_EQ(2, p->value);
     p = p->next;
     EXPECT_EQ(1, p->value);
     EXPECT_EQ(NULL, p->next);


     destroyListNode(list);
}