How do you add two numbers represented by linked lists ??

Problem statement:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }

    Node() {
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}

public class AddTwoNumbers {
    static Node head = null;

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);

        n1.next = n2;
        n2.next = n3;

        Node n4 = new Node(1);
        Node n5 = new Node(2);
        Node n6 = new Node(3);

        n4.next = n5;
        n5.next = n6;

        Node result = calculate(n1, n4);
        System.out.println(result);
    }

    static Node calculate(Node a, Node b) {
        //        //FIXME: Write your logic
        //  1, 2, 3
        //  1, 2, 3
        int carry = 0;

        while (a != null && b != null) {
            addLast(a.data + b.data);

            a = a.next;
            b = b.next;
        }
        return head;
    }

    public static void addLast(int data) {

        if (head == null) {
            head = new Node(data);
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = new Node(data);
    }
}

Output:

Node{data=2, next=Node{data=4, next=Node{data=6, next=null}}}

Reverse a LinkedList

Problem statement: Reverse a LinkedList in java !

1. class Node5 {
2. Node5 next;
3. int data;
4. 
   
5. Node5(int data) {
6. this.data = data;
7. }
8. } // end of Node5
9. 
   
10. public class ReverseLinkedList {
11. 
    
12. Node5 head;
13. 
    
14. public static void main(String[] args) {
15. ReverseLinkedList l = new ReverseLinkedList();
16. l.add(3);
17. l.add(5);
18. l.add(8);
19. l.add(9);
20. l.print(l.head);
21. l.reverse();
22. System.out.println("\nafter reverse linked list");
23. l.print(l.head);
24. } // end of main()
25. 
    
26. // add the element in LinkedList
27. public void add(int data) {
28. Node5 next = new Node5(data);
29. if (head == null) {
30. head = next;
31. return;
32. }
33. Node5 last = head;
34. while (last.next != null) {
35. last = last.next;
36. }
37. last.next = next;
38. } // end of add()
39. 
    
40. // print the LinkedList
41. void print(Node5 next) {
42. Node5 temp = next;
43. while (temp != null) {
44. System.out.print(temp.data + "-->");
45. temp = temp.next;
46. }
47. } // end of print()
48. 
    
49. // reverse the LinkedList
50. Node5 reverse() {
51. Node5 prev = null;
52. Node5 current = head;
53. Node5 next = null;
54. while (current != null) {
55. next = current.next;
56. current.next = prev;
57. prev = current;
58. current = next;
59. }
60. head = prev;
61. return head;
62. } // end of reverse()
63. } //end of ReverseLinkedList 

Output: 

3-->5-->8-->9-->

after reverse linked list

9-->8-->5-->3-->

LinkedList implementation

Problem statement: LinkedList implementation in java !!

1. class A {
2. A n;
3. int data;
4. A(int data) {
5. this.data = data;
6. }
7. }
8. public class LinkedList {
9. A head;
10. 
    
11. /*public static void main(String[] args) {
12. 
    
13. add(1);
14. add(2);
15. print(head);
16. */
17. 
    
18. /*
19. A head = new A(1);
20. A h1 = new A(2);
21. A h2 = new A(3);
22. A h3 = new A(4);
23. A h4 = new A(5);
24. A h5 = new A(6);
25. 
    
26. head.n=h1; h1.n=h2; h2.n=h3;h3.n=h4;h4.n=h5;//h5.n=null;
27. 
    
28. print(head);
29. 
    
30. /*A head = new A();
31. head.data=1;
32. head.n=null;
33. 
    
34. A h1 = new A();
35. h1.data=2;
36. h1.n=null;
37. 
    
38. head.n=h1;
39. 
    
40. A h2 = new A();
41. h2.data=3;
42. h2.n=null;
43. 
    
44. h1.n=h2;
45. 
    
46. A h3 = new A();
47. h3.data=4;
48. h3.n=null;
49. 
    
50. h2.n=h3;
51. 
    
52. A h4 = new A();
53. h4.data=5;
54. h4.n=null;
55. 
    
56. h3.n=h4;
57. */
58. /* System.out.println(head.data); h.data;
59. System.out.println(head.n.data);h=h.n; h.data;
60. System.out.println(head.n.n.data); h=h.n.n;h.data;
61. System.out.println(head.n.n.n.data);h=h.n.n.n;h.data;
62. System.out.println(head.n.n.n.n.data);h=h.n.n.n.n;h.data;
63. 
    
64. print(head);
65. */
66. //}
67. 
    
68. // print the LinkedList
69. public  void print(A head){
70. A temp=head;
71. while(temp!=null){
72. System.out.println(temp.data);
73. temp=temp.n;
74. }
75. }
76. 
    
77. // add the element in LinkedList
78. public void add(int data) {
79. A new_node = new A(data);
80. 
    
81. if (head == null) {
82. head = new_node;
83. return;
84. }
85. A last = head;
86. while (last.n != null) {
87. last = last.n;
88. }
89. last.n = new_node;
90. }
91. 
    
92. // reverse the LinkedList
93. A reverse() {
94. A prev = null;
95. A current = head;
96. A next = null;
97. while (current != null) {
98. next = current.n;
99. current.n = prev;
100. prev = current;
101. current = next;
102. }
103. head = prev;
104. return head;
105. }
106. }

MainUser class:

1. public class MyLinkedList {
2. 
   
3. public static void main(String[] args) {
4. LinkedList l = new LinkedList();
5. l.add(1);
6. l.add(2);
7. 
   
8. l.print(l.head);
9. 
   
10. l.reverse();
11. System.out.println("-----------");
12. l.print(l.head);
13. }
14. }

Output:
1
2
-----------
2
1

LinkedList high level implementation [i]

Problem statement: LinkedList high level implementation in java !

1. class Node4 {
2. Node4 next;
3. int data;
4. 
   
5. Node4(int data) {
6. this.data = data;
7. }
8. }
9. public class LinkedListHighLevelExe1 {
10. Node4 head;
11. 
    
12. public static void main(String[] args) {
13. LinkedListHighLevelExe1 l = new LinkedListHighLevelExe1();
14. l.add(3);
15. l.add(5);
16. l.add(8);
17. l.add(9);
18. l.print(l.head);
19. }
20. 
    
21. // add the element in LinkedList
22. public void add(int data) {
23. Node4 next = new Node4(data);
24. if (head == null) {
25. head = next;
26. return;
27. }
28. Node4 last = head;
29. while (last.next != null) {
30. last = last.next;
31. }
32. last.next = next;
33. }
34. // print the LinkedList
35. void print(Node4 next) {
36. Node4 temp = next;
37. while (temp != null) {
38. System.out.print(temp.data + "-->");
39. temp = temp.next;
40. }
41. }
42. }

Output:

3-->5-->8-->9-->

LinkedList low level implementation [v]

Problem statement: LinkedList low level implementation in java !

1. class Node3 {
2. Node3 next;
3. int data;
4. 
   
5. Node3(int data) {
6. this.data = data;
7. }
8. }
9. 
   
10. public class LinkedListLowLevelExe5 {
11. public static void main(String[] args) {
12. 
    
13. Node3 head = new Node3(9);
14. Node3 h2 = new Node3(2);
15. Node3 h3 = new Node3(4);
16. Node3 h4 = new Node3(5);
17. Node3 h5 = new Node3(8);
18. Node3 h6 = new Node3(9);
19. 
    
20. // linking the obj reference with the next
21. head.next = h2;
22. h2.next = h3;
23. h3.next = h4;
24. h4.next = h5;
25. h5.next = h6;
26. // h6.next = null;
27. 
    
28. print(head);
29. 
    
30. }
31. 
    
32. static void print(Node3 next) {
33. Node3 temp = next;
34. while (temp != null) {
35. System.out.print(temp.data + "-->");
36. temp = temp.next;
37. }
38. }
39. }

Output:
9-->2-->4-->5-->8-->9-->

LinkedList low level implementation [iv]

Problem statement: LinkedList low level implementation in java !

1. class Node2 {
2. Node2 next;
3. int data;
4. 
   
5. Node2(int data) {
6. this.data = data;
7. }
8. }
9. 
   
10. public class LinkedListLowLevelExe4 {
11. public static void main(String[] args) {
12. Node2 head = new Node2(4);
13. Node2 h2 = new Node2(5);
14. Node2 h3 = new Node2(6);
15. Node2 h4 = new Node2(8);
16. 
    
17. head.next = h2;
18. h2.next = h3;
19. h3.next = h4;
20. h4.next = null;
21. print(head);
22. }
23. 
    
24. public static void print(Node2 next) {
25. Node2 temp = next;
26. while (temp != null) {
27. System.out.print(temp.data + "-->");
28. temp = temp.next;
29. }
30. }
31. }

Output:
4-->5-->6-->8-->

LinkedList low level implementation [iii]

Problem statement: LinkedList low level implementation in java !

1. class Node1 {
2. Node1 next;
3. int data;
4. 
   
5. Node1(int data) {
6. this.data = data;
7. }
8. }
9. 
   
10. public class LinkedListLowLevelExe3 {
11. public static void main(String[] args) {
12. Node1 head = new Node1(2);
13. Node1 h2 = new Node1(5);
14. Node1 h3 = new Node1(6);
15. Node1 h4 = new Node1(3);
16. Node1 h5 = new Node1(9);
17. 
    
18. head.next = h2;
19. h2.next = h3;
20. h3.next = h4;
21. h4.next = h5;
22. h5.next = null;
23. 
    
24. System.out.print(head.data + "-->");
25. System.out.print(head.next.data + "-->");
26. System.out.print(head.next.next.data + "-->");
27. System.out.print(head.next.next.next.data + "-->");
28. System.out.print(head.next.next.next.next.data+"-->NULL");
29. }
30. }

Output:
2-->5-->6-->3-->9-->NULL

LinkedList low level implementaion [ii]

Problem statement: LinkedList low level implementation in java !

1. class Node {
2. Node next;
3. int data;
4. }
5. 
   
6. public class LinkedListLowLevelExe2 {
7. public static void main(String[] args) {
8. 
   
9. Node head = new Node();
10. head.next = null;
11. head.data = 1;
12. 
    
13. Node h2 = new Node();
14. h2.next = null;
15. h2.data = 2;
16. 
    
17. Node h3 = new Node();
18. h3.next = null;
19. h3.data = 5;
20. 
    
21. Node h4 = new Node();
22. h4.next = null;
23. h4.data = 8;
24. 
    
25. Node h5 = new Node();
26. h5.next = null;
27. h5.data = 9;
28. 
    
29. head.next = h2;
30. h2.next = h3;
31. h3.next = h4;
32. h4.next = h5;
33. h5.next = null;
34. 
    
35. System.out.print(head.data + "-->"); // head.data
36. System.out.print(head.next.data + "-->"); // head = head.next; head.data
37. System.out.print(head.next.next.data + "-->"); // head = head.next.next; head.data
38. System.out.print(head.next.next.next.data+"-->"); // head = head.next.next.next; head.data
39. System.out.print(head.next.next.next.next.data); // head = head.next.next..next.next; head.data
40. }
41. }

Output:

1-->2-->5-->8-->9

LinkedList low level implementation [i]

Problem statement: LinkedList low level implementation in java !

1. class A1 {
2. A1 n;
3. int data;
4. }
5. 
   
6. public class LinkedListLowLevelExe1 {
7. A head;
8. 
   
9. public static void main(String[] args) {
10. 
    
11. A1 head = new A1();
12. head.data = 1;
13. head.n = null;
14. 
    
15. A1 h1 = new A1();
16. h1.data = 2;
17. h1.n = null;
18. 
    
19. head.n = h1;
20. 
    
21. A1 h2 = new A1();
22. h2.data = 3;
23. h2.n = null;
24. 
    
25. h1.n = h2;
26. 
    
27. A1 h3 = new A1();
28. h3.data = 4;
29. h3.n = null;
30. 
    
31. h2.n = h3;
32. 
    
33. A1 h4 = new A1();
34. h4.data = 5;
35. h4.n = null;
36. 
    
37. h3.n = h4;
38. System.out.println(head.data); // h.data;
39. System.out.println(head.n.data); // h=h.n; h.data;
40. System.out.println(head.n.n.data); // h=h.n.n;h.data;
41. System.out.println(head.n.n.n.data); // h=h.n.n.n;h.data;
42. System.out.println(head.n.n.n.n.data); // h=h.n.n.n.n;h.data;
43. }
44. }

Output:

1

2

3

4

5