Reorder List

Reorder List: You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

The number of nodes in the list is in the range [1, 5 * 10^4].
1 <= Node.val <= 1000

Try this Problem on your own or check similar problems:

Delete the Middle Node of a Linked List

Solution:

Java
JavaScript
Python
C++

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

      ListNode dummy = new ListNode(-1, head);
      ListNode slow = dummy, fast = dummy;

      while(fast != null && fast.next != null){
          fast = fast.next.next;
          slow = slow.next;
      }

      ListNode secondHalfHead = slow.next;
      slow.next = null;
      secondHalfHead = reverseList(secondHalfHead);
      mergeLists(head, secondHalfHead);
  }

  private void mergeLists(ListNode l1, ListNode l2){
      ListNode iter = l1;
      boolean switchToSecondList = true;
      l1 = l1.next;
      while(l1 != null && l2 != null){
          iter.next = switchToSecondList ? l2 : l1;
          if(switchToSecondList){
              l2 = l2.next;
          }else{
              l1 = l1.next;
          }
          switchToSecondList = !switchToSecondList;
          iter = iter.next;
      }
      if(l1 != null || l2 != null){
          iter.next = l1 != null ? l1 : l2;
      }
  }

  private ListNode reverseList(ListNode head) {
      if(head == null || head.next == null) return head;

      ListNode prev = null, next = head, curr = prev;

      while(next != null){
          curr = next;
          next = next.next;
          curr.next = prev;
          prev = curr;
      }

      return prev;
  }
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function (head) {
  if (head == null || head.next == null) return;

  let dummy = new ListNode(-1, head);
  let slow = dummy,
    fast = dummy;

  while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
  }

  let secondHalfHead = slow.next;
  slow.next = null;
  secondHalfHead = reverseList(secondHalfHead);
  mergeLists(head, secondHalfHead);
};

function mergeLists(l1, l2) {
  let iter = l1;
  let switchToSecondList = true;
  l1 = l1.next;
  while (l1 != null && l2 != null) {
    iter.next = switchToSecondList ? l2 : l1;
    if (switchToSecondList) {
      l2 = l2.next;
    } else {
      l1 = l1.next;
    }
    switchToSecondList = !switchToSecondList;
    iter = iter.next;
  }
  if (l1 != null || l2 != null) {
    iter.next = l1 != null ? l1 : l2;
  }
}

function reverseList(head) {
  if (head == null || head.next == null) return head;

  let prev = null,
    next = head,
    curr = prev;

  while (next != null) {
    curr = next;
    next = next.next;
    curr.next = prev;
    prev = curr;
  }

  return prev;
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if head is None or head.next is None:
            return

        dummy = ListNode(-1, head)
        slow = dummy
        fast = dummy

        while fast is not None and fast.next is not None:
            fast = fast.next.next
            slow = slow.next

        secondHalfHead = slow.next
        slow.next = None
        secondHalfHead = self.reverseList(secondHalfHead)
        self.mergeLists(head, secondHalfHead)

    def mergeLists(self, l1: ListNode, l2: ListNode) -> None:
        iter = l1
        switchToSecondList = True
        l1 = l1.next

        while l1 is not None and l2 is not None:
            iter.next = l2 if switchToSecondList else l1
            if switchToSecondList:
                l2 = l2.next
            else:
                l1 = l1.next
            switchToSecondList = not switchToSecondList
            iter = iter.next

        if l1 is not None or l2 is not None:
            iter.next = l1 if l1 is not None else l2

    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        prev = None
        curr = head

        while curr is not None:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        return prev

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return;

        ListNode* dummy = new ListNode(-1, head);
        ListNode* slow = dummy;
        ListNode* fast = dummy;

        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode* secondHalfHead = slow->next;
        slow->next = nullptr;
        secondHalfHead = reverseList(secondHalfHead);
        mergeLists(head, secondHalfHead);
    }

private:
  void mergeLists(ListNode* l1, ListNode* l2) {
      ListNode* iter = l1;
      bool switchToSecondList = true;
      l1 = l1->next;

      while (l1 != nullptr && l2 != nullptr) {
          iter->next = switchToSecondList ? l2 : l1;
          if (switchToSecondList) {
              l2 = l2->next;
          } else {
              l1 = l1->next;
          }
          switchToSecondList = !switchToSecondList;
          iter = iter->next;
      }

      if (l1 != nullptr || l2 != nullptr) {
          iter->next = l1 != nullptr ? l1 : l2;
      }
  }


  ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;

        ListNode* prev = nullptr;
        ListNode* curr = head;

        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
};

Time/Space Complexity:

Time Complexity: O(n)
Space Complexity: O(1)

Explanation:

We separate the list into two by finding the middle node just as we did in the Sort List and the use the reverseList function we implemented in Reverse Linked List to reverse the second half. Now the bulk of the algorithm is in the merge function mergeLists, it's like odd/even switches, first time is even second time odd, third time even and so on. The same goes for picking the next node, we first take from the first list, then from second, then again from the first one. We define switchToSecondList that oscillates between true and false every loop iteration and helps us decide from which list to take the next node. We have linear time complexity proportional to the number of nodes in the linked list given as the input to the function.

Example 1:​

Example 2:​

Constraints:​

Solution:​

Time/Space Complexity:​