Add Two Numbers Represented by Linked Lists – Java Program

This Java program demonstrates how to add two numbers that are represented by linked lists. Each node in the linked list represents a single digit, with the head of the list representing the least significant digit.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list.
2. AddTwoNumbers Class: Contains the method to add two numbers represented by linked lists.
3. Main Class: Contains the main method to execute the program and test the addition functionality.

Java Code

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public class AddTwoNumbers {
        /**
         * Adds two numbers represented by linked lists.
         * 
         * @param l1 The head of the first linked list.
         * @param l2 The head of the second linked list.
         * @return The head of the linked list representing the sum.
         */
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode dummy = new ListNode(0);
            ListNode p = l1, q = l2, current = dummy;
            int carry = 0;
            
            while (p != null || q != null) {
                int x = (p != null) ? p.val : 0;
                int y = (q != null) ? q.val : 0;
                int sum = carry + x + y;
                carry = sum / 10;
                current.next = new ListNode(sum % 10);
                current = current.next;
                
                if (p != null) p = p.next;
                if (q != null) q = q.next;
            }
            
            if (carry > 0) {
                current.next = new ListNode(carry);
            }
            
            return dummy.next;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create two linked lists for testing
            ListNode l1 = new ListNode(2, new ListNode(4, new ListNode(3))); // Represents number 342
            ListNode l2 = new ListNode(5, new ListNode(6, new ListNode(4))); // Represents number 465
            
            // Add the two numbers
            AddTwoNumbers adder = new AddTwoNumbers();
            ListNode result = adder.addTwoNumbers(l1, l2);
            
            // Print the result
            System.out.println("Sum of the two numbers represented by linked lists:");
            printList(result);
        }
        
        // Helper method to print the linked list
        private static void printList(ListNode head) {
            ListNode current = head;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
            System.out.println();
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list. Each node contains an integer value and a reference to the next node.

AddTwoNumbers Class: This class contains the method addTwoNumbers that adds two numbers represented by linked lists. It uses a dummy node to simplify the addition process, handles the carry from the addition, and creates a new list for the result.

Main Class: This class is used for testing the addition functionality. It creates two sample linked lists, adds them using the AddTwoNumbers class, and prints the resulting sum.