# My accepted Java solution in O(n)

• public class Solution {

``````  if ((head == null) || (head.next == null)) return;
ListNode middle;
ListNode p1;
ListNode p2;
ListNode temp;
ListNode middle_next;
boolean even = false;

middle_next = middle.next;
middle.next = null;
p2 = reverseList(middle_next);

while ((p1 != null) && (p2 != null)) {
if (even == false) {
temp = p1.next;
p1.next = p2;
p1 = temp;
even = !even;
}
else {
temp = p2.next;
p2.next = p1;
p2 = temp;
even = !even;
}
}
}

while((fast.next != null) && (fast.next.next != null)) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

private ListNode reverseList (ListNode head) {
ListNode next_next;

while (next != null) {
next_next = next.next;
cur.next = null;
next.next = cur;
cur = next;
next = next_next;
}
• This version is easy to understand. I have some improvement. It is guaranteed that `p1.length<=p2.length`, we don't need to use `boolean even`, we can advance p1 and p2 in one iteration. Plus, we only need to check `if(p1==null)` then break.