Leetcode 143 (Java): Reorder Linked List

Problem: Given the head of a singly linked list. The list can be represented as:

L0 --> L1 --> L2 --> ... --> Ln-1 --> Ln

Reorder the list to be of the following form:

L0 --> Ln --> L1 --> Ln-1 --> ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example:
Input: (1) --> (2) --> (3) --> (4) --> null
Output: (1) --> (4) --> (2) --> (3) --> null

Example:
Input: (1) --> (2) --> (3) --> (4) --> (5) --> null
Output: (1) --> (5) --> (2) --> (4) --> (3) --> null

Constraints:

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

Solution

A brute force algorithm to solve this problem would be to initialize a current pointer, navigate to the end of the linked list for each current pointer, and place the last node of the linked list as the next pointer of the current pointer. However, the time complexity for this solution is O(n^2) because we will be iterating through the linked list n times. The space complexity, however, is O(1).

A better solution would be to find the middle node of the linked list, reverse the second half of the linked list and then merge the first and second halves to the linked list.

Example:
(1) --> (2) --> (3) --> (4) --> (5) --> (6) --> null

Middle node:
middle
(1) --> (2) --> (3) --> (4) --> (5) --> (6) --> null

To find the middle node, we declare two pointers: fast and slow and initialize them to head of the linked list. The slow node traverses the nodes one after the other. The fast node traverses the nodes by skipping one node in each iteration making it twice as fast as the slow now. Therefore, by the time the fast node reaches the end of the linked list, the slow node would have reached the middle node.

ListNode slow = head;
ListNode fast = head;

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

Reverse the second half:
next
previous (4) --> (5) --> (6) --> null
current

                 next

previous <-- (4) (5) --> (6) --> null
current

     previous        next

null <-- (4) (5) --> (6) --> null
current

             previous        next

null <-- (4) <-- (5) (6) --> null
current

                     previous

null <-- (4) <-- (5) <-- (6) null
current

To reverse the second half of the linked list, we declare a current pointer and assign the slow pointer to it. Therefore, the current node points to the middle node of the linked list. We also assign two pointers, previous and next and assign them to null. previous will hold the current node when current moves on to the next pointer. This way we keep track of three pointers: previous, current and next.

We traverse through the second half of the linked list through the current pointer until we reach the end. For each iteration, we assign the next pointer to the next of current. We then assign the next of the current to the previous pointer. This way we are flipping the direction of the next pointers. We then assign the current to previous and next to current. This way all three pointers move one node forward while changing the order of the current node.

ListNode previous = null;
ListNode current = slow;
ListNode next = null;

while(current != null) {
  next = current.next;
  current.next = previous;
  previous = current;
  current = next;
}

This will make the previous node the second half in the reversed order.

Merge both halves:
(1) --> (6) --> (2) --> (5) --> (3) --> (4) --> null

By now, we have the second half of the linked list reversed. We need to assume both halves as two different linked lists and merge them and adjust the null pointer at the end accordingly.

ListNode first = head;
ListNode second = previous;
ListNode temp = head;

while(second.next != null) {
  temp = temp.next;
  first.next = second;
  second = second.next;
  first.next.next = temp;
  first = first.next.next;
}

Code

public ListNode reorder(ListNode head) {
  if(head == null) {
    return head;
  }


  // Find the middle node
  ListNode slow = head;
  ListNode fast = head;

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

  // Reverse the second half of the linked list
  ListNode previous = null;
  ListNode current = slow;
  ListNode next = null;

  while(current != null) {
    next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }

  // Merge both halves
  ListNode first = head;
  ListNode second = previous;
  ListNode temp = head;

  while(second.next != null) {
    temp = temp.next;
    first.next = second;
    second = second.next;
    first.next.next = temp;
    first = first.next.next;
  }
  return head;
}

The time complexity of the above algorithm is O(n), whereas the space complexity if O(1).