import java.io.*;
import java.util.*;

// Define the structure of a node in the linked list
class Node {
  int data;
  Node next;
  Node(int x)
  {
    data = x;
    next = null;
  }
}

class GFG {

  // Function to return the reverse of a linked list
  static Node reverseList(Node head)
  {
    Node prev = null;
    Node cur = head;
    Node next_;
    while (cur != null) {
      next_ = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next_;
    }
    return prev;
  }

  // Function to return the sum of two linked lists
  static Node addTwoLists(Node l1, Node l2)
  {
    Node dummy = new Node(0);
    Node cur = dummy;
    int carry = 0;

    while (l1 != null || l2 != null) {
      int x = l1 != null ? l1.data : 0;
      int y = l2 != null ? l2.data : 0;
      int sum = carry + x + y;
      carry = sum / 10;
      cur.next = new Node(sum % 10);
      cur = cur.next;
      if (l1 != null) {
        l1 = l1.next;
      }
      if (l2 != null) {
        l2 = l2.next;
      }
    }
    if (carry > 0) {
      cur.next = new Node(carry);
    }
    return dummy.next;
  }

  // Function to print a linked list
  static void printList(Node head)
  {
    while (head != null) {
      System.out.print(head.data + " ");
      head = head.next;
    }
    System.out.println();
  }

  // Function to create a copy of a linked list
  static Node copyList(Node head)
  {
    Node cur = head;
    Node dummy = new Node(0);
    Node copy = dummy;

    while (cur != null) {
      copy.next = new Node(cur.data);
      copy = copy.next;
      cur = cur.next;
    }
    return dummy.next;
  }

  public static void main(String[] args)
  {
    // Example linked list:
    // 1 -> 2 -> 3 -> 4
    Node head1 = new Node(1);
    head1.next = new Node(2);
    head1.next.next = new Node(3);
    head1.next.next.next = new Node(4);

    // Printing original linked list
    System.out.print("Original linked list : ");
    printList(head1);

    // Step1 - Make a copy of original linked list
    Node newList = copyList(head1);

    // Step2 - Reverse a linked list
    Node head2 = reverseList(newList);

    // Printing reversed linked list
    System.out.print("Reversed linked list : ");
    printList(head2);

    // Step3 - Addition of a original linked list and
    // its reverse
    Node addition = addTwoLists(head1, head2);

    // Step4 - Reverse a addition Linked list
    Node result = reverseList(addition);

    // Step5 - Print the resultant linked list
    System.out.print("Resultant linked list : ");
    printList(result);
  }
}