PU Reorder List

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void reorderList(struct ListNode* head) {
    if (!head || !head->next) return;
    struct ListNode *l = head, *r = head->next;
    while (r && r->next) {
        l = l->next;
        r = r->next->next;
    }
    r = l->next;
    while (r->next) {
        struct ListNode *tmp = r->next;
        r->next = r->next->next;
        tmp->next = l->next;
        l->next = tmp;
    }
    r = l->next;
    l->next = 0;
    while (r) {
        struct ListNode *tmp = r->next;
        r->next = head->next;
        head->next = r;
        head = r->next;
        r = tmp;
    }
}

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if not head or not head.next: return
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        tail = slow.next
        while tail.next:
            cur = tail.next
            slow.next, cur.next, tail.next = cur, slow.next, cur.next

        r = slow.next
        slow.next = None
        l = head
        while r:
            tmp = r.next
            l.next, r.next = r, l.next
            l = r.next
            r = tmp