Solution 1Node Array

  • TimeO(n)
  • SpaceO(n)

where, n is the number of nodes in the linked list.
This is the most easiest to implement solution intuitively, however the most optimal solution uses O(1) space, look for below approach.

Python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(n)
    where, n is the number of nodes in the linked list.
    This is the most easiest to implement solution intuitively, 
    however the most optimal solution uses O(1) space, look for below approach.
    '''
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        order = []
        node = head
        while node:
            order.append(node)
            node = node.next
        node = head
        for i in range(len(order)-1,len(order)//2,-1):
            temp = node.next
            node.next = order[i]
            order[i-1].next = None
            order[i].next = temp
            node = temp
Leet Code/python.py · L1059–1088

Solution 2Reverse Merge

  • TimeO(n)
  • SpaceO(1)

where, n is the number of nodes in the linked list.
This is the most optimal solution using O(1) space.
You use 2 pointers, 1 fast and 1 slow to find the middle of the linked list, then reverse the second half of the linked list, finally merge the 2 halves by alternating nodes from each half.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(1)
    where, n is the number of nodes in the linked list.
    This is the most optimal solution using O(1) space.
    You use 2 pointers, 1 fast and 1 slow to find the middle of the linked list,
    then reverse the second half of the linked list,
    finally merge the 2 halves by alternating nodes from each half.
    '''
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # find middle
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # reverse second half
        second = slow.next
        prev = slow.next = None
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp

        # merge two halfs
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2
Leet Code/python.py · L1090–1131
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public void reorderList(ListNode head) {
    ListNode slowPointer = head;
    ListNode fastPointer = head;
    while (fastPointer.next != null) {
        fastPointer = fastPointer.next;
        if (fastPointer.next != null) {
            fastPointer = fastPointer.next;
            slowPointer = slowPointer.next;
        }
    }

    ListNode prev = null;
    ListNode cur = slowPointer.next;
    slowPointer.next = null;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }

    slowPointer = head;
    while (slowPointer != null && fastPointer != null) {
        cur = slowPointer.next;
        slowPointer.next = fastPointer;
        slowPointer = cur;
        prev = fastPointer.next;
        fastPointer.next = cur;
        fastPointer = prev;
    }
}
Leet Code/java.java · L815–856