Code to reverse singly-linked list.HEADmaster

1 files changed, 83 insertions, 0 deletions

diff --git a/reverse-list.cpp b/reverse-list.cpp
new file mode 100644
index 0000000..f5040af
--- /dev/null
+++ b/reverse-list.cpp
@@ -0,0 +1,83 @@
+
+#include <cstdlib>
+#include <iostream>
+
+using namespace std;
+
+struct node {
+    const char* value;
+    node* next;
+};
+
+void reverse(node*& start)
+{
+    if (!start)
+        return;
+
+    // Set the previous and current nodes.
+    node* p0 = start;
+    node* p1 = p0->next;
+    p0->next = NULL;
+
+    while (p1)
+    {
+        node* p2 = p1->next; // store the next node.
+        p1->next = p0; // set the next of the current node to the previous node.
+
+        // Update the previous and current nodes for the next iteration.
+        p0 = p1;
+        p1 = p2;
+    }
+
+    start = p0;
+}
+
+const char* strs[] = {
+    "A", "B", "C", "D", "E", "F", 0
+};
+
+void populate(node*& start)
+{
+    // We assume the static string array is never empty.
+    const char** p = strs;
+
+    // Create the first node.
+    node* first = new node;
+    first->value = *p;
+    first->next = NULL;
+
+    node* cur = first;
+    node* prev = NULL;
+    for (++p; *p; ++p)
+    {
+        cur->next = new node;
+        cur->next->value = *p;
+        cur->next->next = NULL;
+
+        prev = cur;
+        cur = prev->next;
+    }
+
+    start = first;
+}
+
+void print(const node* start)
+{
+    for (const node* p = start; p; p = p->next)
+        cout << p->value << " ";
+    cout << endl;
+}
+
+int main()
+{
+    node* slist = NULL;
+    populate(slist);
+    cout << "input: ";
+    print(slist);
+    reverse(slist);
+    cout << "output: ";
+    print(slist);
+
+    // TODO: De-allocate the list.
+    return EXIT_SUCCESS;
+}