Skip to content

Instantly share code, notes, and snippets.

@jsundram
Created January 27, 2011 01:32
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jsundram/797898 to your computer and use it in GitHub Desktop.
Save jsundram/797898 to your computer and use it in GitHub Desktop.
reverse last 5 nodes of a linked list
// Here's what the linked list looks like.
// I've assumed int values, so you can see that it works
class Node
{
public:
Node() : next(NULL), value(0) {}
Node(int v) : next(NULL), value(v){}
Node* next;
int value;
};
int length(Node* head)
{
int n = 0;
for (Node* curr = head; curr != NULL; curr = curr->next)
n++;
return n;
}
Node* reverse(Node* ptr)
{
Node* temp;
Node* prev = NULL;
while (ptr != NULL)
{
temp = ptr->next;
ptr->next = prev;
prev = ptr;
ptr = temp;
}
return prev;
}
void reverse_last(Node* head, n)
{
int n = length(head);
Node* e = head;
for (int i = 0; i < n-5-1; i++)
e = e->next;
e->next = reverse(e->next);
}
int main()
{
// initialize a list of length n.
int n = 10;
Node* head = new Node(0);
Node* curr = head;
for (int i = 1; i < n; i++)
{
Node* t = new Node(i);
curr->next = t;
curr = t;
}
// do the reversal
reverse_last(head, 5);
// print what we've got
for (Node* curr = head; curr != NULL; curr = curr->next)
std::cout << curr->value << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment