Zip a list

The zip of a list is creating a new list by having 2 pointers one from the start and one from the end and picking one node each and merging into a new list.

Example

List: 1,2,3,4,5,6
Zip:  1,6,2,5,3,4

Solution

• Split the list in the middle, into 2 lists

    def split
    slow = @head
    fast = @head
    prev = slow
  
    while slow && fast && fast.next
      prev = slow
      slow = slow.next
      fast = fast.next.next
    end
  
    prev.next = nil
    slow
  end
  

• Reverse the second list

    def reverse(head)
        puts 'Reversing ..'
  
        return nil if head.nil?
        return head if head.next.nil?
  
        if head.next.next.nil?
          prev = head
          curr = prev.next
          curr.next = prev
          prev.next = nil
          head = curr
          return head
        end
  
        prev = head
        curr = prev.next
        fwd = prev.next.next
        prev.next = nil
  
        while fwd.next != nil
          curr.next = prev
          prev = curr
          curr = fwd
          fwd = fwd.next
        end
  
        fwd.next = curr
        curr.next = prev
  
        fwd
    end
  

• Now merge the 2 lists

    def merge_list(first, second)
        return second if first.nil?
        return first if second.nil?
  
        head = first
        curr = first
        first = first.next
  
        while(first && second)
          curr.next = second
          second = second.next
          curr = curr.next
          curr.next = first
          first = first.next
          curr = curr.next
        end
  
        if first
          curr.next = first
        elsif second
          curr.next = second
        end
  
        head
    end
  

• At a high level zip function looks like this

    def zip
        return if @head.next.nil?
        return if @head.next.next.nil?
  
        first = @head
        second = split
        second = reverse(second)
  
        @head = merge_list(first, second)
    end
  

Time complexity

• O(n) to split
• O(n) to reverse
• O(n) to merge
• Overall O(n)