Re-Order LinkedList

Reorder the given singly-linked list N1 -> N2 -> N3 -> N4 -> … -> Nn -> null to be N1- > Nn -> N2 -> Nn-1 -> N3 -> Nn-2 -> … -> null

Examples

• L = null, is reordered to null

• L = 1 -> null, is reordered to 1 -> null

• L = 1 -> 2 -> 3 -> 4 -> null, is reordered to 1 -> 4 -> 2 -> 3 -> null

• L = 1 -> 2 -> 3 -> null, is reordered to 1 -> 3 -> 2 -> null

Solution: Cut, Reverse, Merge

/**
 * class ListNode {
 *   public int value;
 *   public ListNode next;
 *   public ListNode(int value) {
 *     this.value = value;
 *     next = null;
 *   }
 * }
 */
public class Solution {
  public ListNode reorder(ListNode head) {

    if(head == null || head.next == null) return head;
    // Write your solution here
    int n = getLength(head);

    int middle = n / 2;

    ListNode middleNode = cut(head, middle);

    middleNode = reverse(middleNode);

    ListNode newhead = merge(head, middleNode);

    return newhead;

  }
  
  public ListNode merge(ListNode head, ListNode middle){
    ListNode dummy = new ListNode(0);
    ListNode start = dummy;

    while (head != null){
      ListNode first = head;
      ListNode second = middle;

      head = head.next;
      middle = middle.next;

      dummy.next = first;
      first.next = second;

      dummy = second;
    }

    if (middle != null){
      dummy.next = middle;
    }

    return start.next;
  }

  public int getLength(ListNode head) {
    if (head == null) return 0;

    return 1 + getLength(head.next);
  }

  public ListNode cut(ListNode head, int index) {
    // TODO better checking perhaps
    if (index > getLength(head)) return null;

    for (int i = 0; i < index - 1; i++) {
      head = head.next;
    }
    ListNode res = head.next;
    head.next = null;
    return res;
  }

  public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode newHead = reverse(head.next);

    head.next.next = head;
    head.next = null;
    return newHead;
  }
}

TC: TC O(N) getLength + O(N) reverse second half + O(N) merge = O(3N) = O(N)

SC: O(1) no additional structs used