Reorder Linked List

Question

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.
My solution is something like this.
I get the idea that we first find the middle element, then reverse the list from next element of mid to end and then merge them,but my question is what if, the main function it was something like public ListNode reorderList(ListNode head),then what should i return to get the entire list.Thanks in advance.

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode mid = findMiddle(head);
        ListNode tail = reverse(mid.next);
        mid.next = null;
        merge(head, tail);
    }
       //to find the middle node of linked list
       private ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    //to reverse the nodes in linked list
    private ListNode reverse(ListNode head) {
       ListNode prev = null;
       ListNode curr = head;
       ListNode next = null;
        while(curr!=null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        return head;
    }
    //to merge both the start and tail node.
    private void merge(ListNode headA, ListNode headB) {
        ListNode dummy = new ListNode(0);
        while (headA != null && headB != null) {
            dummy.next = headA;
            headA = headA.next;
            dummy = dummy.next;

            dummy.next = headB;
            headB = headB.next;
            dummy = dummy.next;
        }
        if (headA != null) {
            dummy.next = headA;
        } else if (headB != null) {
            dummy.next = headB;
        }
  } 
}

Answer 1

You would be better to find the last node, remove it, and insert it at your current location. This saves you the hassle of counting and finding the middle.

See the method fold below.

static class MyList<T> {
    Node<T> head;

    class Node<T> {
        final T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    /**
     * Adds the data to the list.
     */
    public void add(T data) {
        Node<T> node = new Node<>(data);
        if ( head == null ) {
            head = node;
        } else {
            last().next = node;
        }
    }

    /**
     * Finds the node previous to the one specified
     */
    private Node<T> prev(Node<T> it) {
        // Singly linked so we must search.
        Node<T> node = head;
        Node<T> prev = null;
        while(node != it && node != null) {
            prev = node;
            node = node.next;
        }
        return node != null ? prev: null;
    }

    /**
     * Finds the last node.
     */
    private Node last() {
        Node<T> last = head;
        // Find the end.
        while(last.next != null) {
            last = last.next;
        }
        return last;
    }

    /**
     * Folds the list back on itself, interleaving as it goes.
     */
    public void fold() {
        Node<T> node = head;
        // For each node.
        while(node != null) {
            // Find last
            Node<T> last = last();
            // Remove it.
            Node<T> prev = prev(last);
            prev.next = null;
            // Insert it here.
            last.next = node.next;
            node.next = last;
            // Step past the added one.
            node = node.next;
            if(node != null) {
                node = node.next;
            }
        }
    }

    /**
     * String version of the list.
     */
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        Node<T> node = head;
        while(node != null) {
            sb.append(node.data).append(",");
            node = node.next;
        }
        // Remove the last comma.
        int comma = sb.lastIndexOf(",");
        if(comma >= 0) {
            sb.deleteCharAt(comma);
        }
        sb.append("]");
        return sb.toString();
    }
}

public void test() {
    MyList<Integer> list = new MyList<>();
    // Numbers 0 to 10.
    for(int i = 0; i < 10; i++) {
        list.add(i);
    }
    // Print it before folding.
    System.out.println(list);
    // Fold it.
    list.fold();
    // Print after folding.
    System.out.println(list);
}