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

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

#programming #linkedlists #java #datastructures

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.

Top comments (0)