/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public void reorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
ListNode preMiddle = slow;
ListNode curr = preMiddle.next;
while (curr.next != null) {
ListNode next = curr.next;
curr.next = next.next;
next.next = preMiddle.next;
preMiddle.next = next;
}
ListNode node = head;
curr = preMiddle.next;
while (node != preMiddle) {
preMiddle.next = curr.next;
curr.next = node.next;
node.next = curr;
node = curr.next;
curr = preMiddle.next;
}
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
private ListNode reverse(ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode next = head.next;
head.next = newHead;
newHead = head;
head = next;
}
return newHead;
}
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
ListNode fast = head, slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
fast = head;
ListNode newHead = reverse(slow.next);
slow.next = null;
ListNode q = newHead;
while (q != null) {
ListNode next = q.next;
q.next = fast.next;
fast.next = q;
fast = q.next;
q = next;
}
return;
}
}