Reverse Lists, Add them, Reverse the sum and return the sum as a List
Tags: programming, linkedlists, java, datastructures
Published: 2021-06-28 10:39:46

I came around this problem while solving questions on leetcode. This is a very good problem of linked lists. Basically the problem says: You are given two linked lists, you have to add those lists by reversing them and again reverse your addition output and return it as a linked list 🤔. I will not go solving this problem in context of time complexity but rather I will try to simplify it to the most basic level.
I'm using Java to solve this problem. I will be solving it from the scratch.

* 1. First let's create a node for the linked list.
```
public class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            next = null;
        }
    }
```
* 2. Function to add Nodes to the linked list:
```
    public Node head = null;
    public Node tail = null;

    public void addNode(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
    }
```
* 3. Function to display nodes in the list.
```
public void display() throws IllegalStateException {
        Node current = head;
        if (head == null) {
            throw new IllegalStateException("Your List is empty");
        }
        while (current != null) {
            System.out.println(current.data);
            current = current.next;
        }
    }
```
The top 3 blocks of codes were normal implementation of the linked list and displaying them using the display function.
Now, the function to reverse the linked list:

* 4. Reversing the linked list iteratively (you can do that recursively also)
```
public Node reverse(Node start) throws IllegalStateException {
        if (start == null) {
            throw new IllegalStateException("List is empty");
        }
        Node current = start;
        Node prev = null;

        while (current != null) {
            Node next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        return prev;
    }
```
* 5. The most important step is to add the values from the list to a StringBuilder and convert it to integer and return it. We'll use this value in the main function.
Workaround: To add the values easily that's why we are doing this extra step.
```
public static int arr(Node start) throws IllegalStateException {
        Node current = start;
        if (start == null) {
            throw new IllegalStateException("Your List is empty");
        }

        StringBuilder sb = new StringBuilder();
      
        while (current != null) {
            sb.append(current.data);
            current = current.next;
        }
        String str = sb.toString();
        int x = Integer.parseInt(str);
        return x; // string converted to int
    }
```
* 6. Finally the main method:
```
public static void main(String[] args) {
        // creating two demo lists 
        AddTwoNumbers list1 = new AddTwoNumbers();
        list1.addNode(1);
        list1.addNode(1);
        list1.addNode(6);

        AddTwoNumbers list2 = new AddTwoNumbers();
        list2.addNode(1);
        list2.addNode(9);
        list2.addNode(2);
        
        // reversing the lists
        Node x1 = list1.reverse(list1.head);
        Node x2 = list2.reverse(list2.head);

        // getting the returned integer representation of the lists
        int y1 = arr(x1);
        int y2 = arr(x2);
        
        // adding both the values that's why we did the 5th step to simplify this summing process
        int sum = y1 + y2;

        // convert again to string builder so that we can reverse it easily
        StringBuilder str = new StringBuilder();
        StringBuilder output = str.append(sum).reverse();

        // create a new list that will be returned
        AddTwoNumbers finalList = new AddTwoNumbers();
         
        // pass the values to the list
        for (int i = 0; i < output.length(); i++) {
            int x =Integer.parseInt(String.valueOf(output.charAt(i)));
            finalList.addNode(x);
        }
        
        // and, finally display it
        finalList.display();

    }
```
I know this solution went too long but this is a good workaround of solving this problem easily.