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)

results matching ""

    No results matching ""