Thursday, August 6, 2015

LeetCode OJ - Reverse Linked List

Problem:

Solution:

Invert the link by the time we walk. To do that we maintain two pointers cursor and previous as follow:

A ->B ->C -> NULL
cursor->A
previous-> NULL.

Now we walk a step forward, the end state we want is this

NULL <- A B->C->NULL
cursor->B
previous->A

Let's walk one more step, then we will get

NULL <- A<-B C->NULL
cursor->C
previous->B

This is the code that make it happens

Code:

#include "stdafx.h"

#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

{
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
{
ListNode* prev = NULL;
while (cursor != NULL)
{
ListNode* next = cursor->next;
cursor->next = prev;
prev = cursor;
cursor = next;
}
return prev;
}
};
};

{
Solution solution;
ListNode a(1);
ListNode b(1);
ListNode c(2);
ListNode d(2);
ListNode e(3);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;

ListNode* result = solution.reverseList(&a);
while (result != NULL)
{
cout << result->val;
cout << ", ";
result = result->next;
}
cout << endl;

return 0;
}