Изменить порядок связанного списка

Question

Дан односвязный список L: L0 → L1 →… → Ln-1 → Ln, изменить его на L0 → Ln → L1 → Ln-1 → L2 → Ln-2 →…

Вы не можете изменять значения в узлах списка, только узлы могут быть изменены.
Мое решение что-то вроде этого.
Я понял, что сначала мы находим средний элемент, затем переворачиваем список со следующего элемента с середины на конец, а затем объединяем их, но мой вопрос в том, что если основной функцией было что-то вроде public ListNode reorderList (ListNode голова) , то что я должен вернуть, чтобы получить весь список. Спасибо заранее.

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

Было бы лучше найти последний узел, удалить его и вставить в текущее местоположение. Это избавит вас от необходимости считать и находить середину.

См. Метод fold ниже.

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);
}