Reverse Linked List in time O(n) & space O(1)

I’m not a dev but I do enjoy a coding challenge. In this blog post I will explain how to reverse a singly linked linked-list.

The data structure looks like this:

A simple code to implement a singly linked linkedlist is:

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

To reverse the list: we need two pointers a previous pointer (prev) and a current one pointing to the current node we’re checking (curr). During exchanging pointers we will also a need a temporary pointer to hold the next pointer so we don’t lose track of our linked list during the reversing process

input: 1->2->3->4
output: 4->3->2->1

Needless to say you need to check for extreme cases such as an empty list, or a 1 element list.

Here is my code:

class Solution {
    ListNode* reverseList(ListNode* head) {
        // handling of an empty or single node list
        if (head == NULL || head->next == NULL) return head;
        ListNode* curr(0); curr=head;
        ListNode* prev(0); prev=NULL;		
        while(curr != NULL)
			ListNode* tmp(0);		
			tmp = curr->next;
			curr->next = prev;
			prev = curr;
			curr = tmp;
        return prev;

we move on the linked list until our current pointer is pointing to null.
We point a tmp pointer to the next node so we don't lose track
we point our current pointer's next pointer to the previous pointer
We move the previous pointer to the current node
then we also do the same with the current node to be poining to the original next node (now stored in tmp). 
we repeat. 

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

This site uses Akismet to reduce spam. Learn how your comment data is processed.