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;
            }
        }
  • 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.

    29

    This website collects cookies to deliver better user experience

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