Reverse a Singly Linked List Recursively in Java

We have already seen how to reverse a singly linked list with illustrative pictures. Now lets see how we can do it recursively. In the previous problem we did it iteratively, now we shall do it recursively.
To attack any problem in a recursive approach, we need to be very clear about the end/boundary conditions. For a linked list, reverse of a null list or reverse of list of size 1 is going to be the same.
Reverse of a linked list of size x will be the reverse of the 'next' element followed by first.
A picture means a thousand words. So, here is what happens internally.

Now for the comprehensive Java code (reference for SinglyLinkedList implementation can be found here)


Cheers,
Bragaadeesh.

Java Program to reverse a Singly Linked List

Hi folks,

I have written an efficient way to reverse a Singly Linked List using three pointers/nodes for traversal/temporary purposes. I have given a pictorial representation of what happens with near, mid and far pointer. The program is mostly self explanatory. Remember, we are using our implementation of Singly Linked List. You may visit this link if you need that class.

Note : You may click on the above image to get a clearer picture.

Now, for the source code.


Cheers,
Bragaadeesh.

Java/C++ Program to reverse the words in a sentence

As an attempt to preparation for data structures and ready-to-code for programs, I thought I will start coding on my own and publish it here. Any discrepancies, bugs if you may find , plz leave a comment.

So, this is a program in java written to reverse the words in a sentence. I thought this was pretty easy using inbuilt method such as split() and StringBuilder(). I could have 'not' used them, but again its writing the whole JFC (Java Foundation Class) implementation. Screw it :), I am on a journey to write lots of programs such as this...

package dsa.stringmanipulation;

public class SentenceReverser {

    public static final String SPACE = " ";

    public static void main(String args[]) {
        SentenceReverser rev = new SentenceReverser();
        System.out.println(rev
                .printReversed("This  is my first attempt at a program in ds"));
    }

    public String printReversed(String inputText) {
        if (inputText != null && inputText.length() > 0) {
            int lenOfText = inputText.length();
            if (lenOfText == 1) {
                return inputText;
            } else {
                String[] texts = inputText.split(SPACE);
                StringBuilder output = new StringBuilder();
                for (int i = texts.length - 1; i > 0; i--) {
                    output.append(texts[i]).append(SPACE);
                }
                output.append(texts[0]);
                return output.toString();
            }
        } else {
            System.out.println("Invalid Sentence");
            return null;
        }
    }
}

Now, for the code in C++,

#include <iostream>

using namespace std;

void str_rev(char s[], int start, int end)
{
        int len = end - start;
        for(int i=0;i<len/2;i++)
        {
                char t = s[i+start];
                s[i+start] = s[end-i-1];
                s[end-i-1] = t;
        }
}

int main()
{
        char a[] = "my name is prabhu";
        cout << "[" << a << "] ==> ";

        str_rev(a,0,strlen(a));

        int start_index = 0;
        for(size_t i=0;i<=strlen(a);i++)
        {
                if(a[i] == ' ' || a[i] == '\0')
                {
                        str_rev(a,start_index,i);
                        start_index = i+1;
                }
        }
        cout << "[" << a << "]" << endl;
}

Cheers,
Bragaadeesh.