DEV Community

Cover image for Reverse Lists, Add them, Reverse the sum and return the sum as a List
Rajesh Ranjan
Rajesh Ranjan

Posted on

3 1

Reverse Lists, Add them, Reverse the sum and return the sum as a List

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;
        }
    }
Enter fullscreen mode Exit fullscreen mode
  • 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;
        }
    }
Enter fullscreen mode Exit fullscreen mode
  • 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;
        }
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode
  • 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
    }
Enter fullscreen mode Exit fullscreen mode
  • 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();

    }
Enter fullscreen mode Exit fullscreen mode

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

Heroku

This site is built on Heroku

Join the ranks of developers at Salesforce, Airbase, DEV, and more who deploy their mission critical applications on Heroku. Sign up today and launch your first app!

Get Started

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay