1
// This Question can be solved easily using two standard methods of LinkedList
2
// 1) addFirst (it adds node in front of the LinkedList)
3
// 2) addLast (it adds node in end of the LinkedList)
4

5
class Solution {
6

7
  static ListNode oh;
8
  static ListNode ot;
9
  static ListNode th;
10
  static ListNode tt;
11

12
  public ListNode reverseEvenLengthGroups(ListNode head) {
13

14
    oh = null;
15
    ot = null;
16
    th = null;
17
    tt = null;
18

19
    if (head == null || head.next == null) return head;
20

21
    int size = length(head);
22
    int idx = 1;
23
    ListNode curr = head;
24
    int group = 1;
25

26
    while (curr != null) {
27
      int temp = size - idx + 1;
28
      if ((temp >= group && group % 2 == 0) || (temp < group && temp % 2 == 0)) {
29
        int k = group;
30
        while (k-- > 0 && curr != null) {
31
          ListNode t = curr.next;
32
          curr.next = null;
33
          addFirst(curr);
34
          curr = t;
35
          idx++;
36
        }
37
      } else {
38
        int k = group;
39
        while (k-- > 0 && curr != null) {
40
          ListNode t = curr.next;
41
          curr.next = null;
42
          addLast(curr);
43
          curr = t;
44
          idx++;
45
        }
46
      }
47

48
      if (oh == null && ot == null) {
49
        oh = th;
50
        ot = tt;
51
      } else {
52
        ot.next = th;
53
        ot = tt;
54
      }
55

56
      th = null;
57
      tt = null;
58
      group++;
59
    }
60

61
    return oh;
62
  }
63

64
  public int length(ListNode head) {
65
    if (head == null) return 0;
66
    ListNode curr = head;
67
    int k = 0;
68
    while (curr != null) {
69
      k++;
70
      curr = curr.next;
71
    }
72
    return k;
73
  }
74

75
  public void addFirst(ListNode head) {
76
    if (tt == null && th == null) {
77
      th = head;
78
      tt = head;
79
    } else {
80
      head.next = th;
81
      th = head;
82
    }
83
  }
84

85
  public void addLast(ListNode head) {
86
    if (tt == null && th == null) {
87
      th = head;
88
      tt = head;
89
    } else {
90
      tt.next = head;
91
      tt = head;
92
    }
93
  }
94
}