content: package linkedlist;
  
  public class ReverseEvenNodes {
  
      /*
       * Given a singly linked list, reverse nodes at even indices:
       * Input: 7, 14, 21, 28, 9
       * Output: 7, 28, 21, 14, 9
       *
       * Runtime Complexity:
       * Linear, O(n)
       *
       * Memory Complexity:
       * Constant, O(1).
       *
       *
       * Create two lists comprising of nodes at odd and even indices.
       * While extracting even nodes, push them at the head of list_even since we need them in reverse order while merging.
       * Now that the two lists are in the correct order, it's just a matter of merging their nodes alternately.
       * */
  
      public static LinkedList.Node mergeAlternating(LinkedList.Node list1,
                                                     LinkedList.Node list2) {
  
          if (list1 == null) {
              return list2;
          }
  
          if (list2 == null) {
              return list1;
          }
  
          LinkedList.Node head = list1;
  
          while (list1.next != null &&
                  list2 != null) {
              LinkedList.Node temp = list2;
              list2 = list2.next;
  
              temp.next = list1.next;
              list1.next = temp;
              list1 = temp.next;
          }
  
          if (list1.next == null) {
              list1.next = list2;
          }
  
          return head;
      }
  
      public static LinkedList.Node reverseEvenNodes(LinkedList.Node head) {
  
          // Let's extract even nodes from the existing
          // list and create a new list consisting of
          // even nodes. We will push the even nodes at
          // head since we want them to be in reverse order.
  
          LinkedList.Node curr = head;
          LinkedList.Node list_even = null;
  
          while (curr != null &&
                  curr.next != null) {
              LinkedList.Node even = curr.next;
              curr.next = even.next;
  
              // Push at the head of new list.
              even.next = list_even;
              list_even = even;
  
              curr = curr.next;
          }
  
          // Now, merge the two lists
          // Original: 1,2,3,4,5
          // Modified original: 1,3,5
          // List_even: 4,2
          // Merged: 1,4,3,2,5
  
          return mergeAlternating(head, list_even);
      }
  
  
      public static class LinkedList {
  
          private Node head;
  
          public Node head() {
              return head;
          }
  
          public void printNode(Node node) {
              while (node != null) {
                  System.out.print(node.data + " ");
                  node = node.next;
              }
          }
  
          /* Inserts a new Node at end of the list. */
          public void push(int new_data) {
              Node newNode = new Node(new_data);
              if (head == null) {
                  head = new Node(new_data);
                  return;
              }
  
              newNode.next = null;
              Node last = head;
              while (last.next != null) {
                  last = last.next;
              }
              last.next = newNode;
          }
  
          public static class Node {
              private Node next;
              private Integer data;
  
              public Node(Integer data) {
                  this.data = data;
              }
  
              public Node next() {
                  return next;
              }
  
              public void setNext(Node next) {
                  this.next = next;
              }
  
              public Integer data() {
                  return data;
              }
  
              public void setData(Integer data) {
                  this.data = data;
              }
          }
      }
  
  
      public static void main(String[] args) {
  
          LinkedList linkedList1 = new LinkedList();
          linkedList1.push(7);
          linkedList1.push(14);
          linkedList1.push(21);
          linkedList1.push(28);
          linkedList1.push(9);
  
          System.out.println("List 1: ");
          linkedList1.printNode(linkedList1.head);
          System.out.println();
  
          LinkedList.Node mergedList = reverseEvenNodes(linkedList1.head);
          linkedList1.printNode(mergedList);
      }
  }
  