Reverse a Linked List with increasing groupsize-- 1, 2, 3...
rishabh
170
Interview

Given a linked list:

a->b->c->d->e->f->....
Reverse it such that
a->c->b->f->e->d->.....

Basically like reverse sublist size 1, 2, 3, 4.....
[a]->[c->b]->[f->e->d]->.....

The correct solution is given below, my approach was wrong, it was a vid round and instead of working it out
on a piece of paper, I tried working it out on the shared IDE, the code editor did not allow me to run the solution,
so I couldn't test its correctness at the time and make the necessary changes.

Any tips how to solve questions like this, which require pencil and paper over a video round, also ensuring that
the entire time does not go into scribbling on paper like a muppet. So I can reverse a linked list in about 5min,
what I'm looking for is speed gains over vid chat. I dove into writing code as soon the question was assigned, and
went on explaining what I was doing.

class ListNode():
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        return f'<ListNode<{self.val}>>'


def reverse(head):
    if not head:
        return

    def helper(node, lim):  # head, tail, next
        if not node:
            return

        prev = None
        current = node

        j = 1
        while current and j <= lim:
            temp = current.next
            current.next = prev

            prev = current
            current = temp
            j += 1

        node.next = current
        return prev, node

    i = 2
    cursor = head.next
    prev = head
    while cursor:
        xhead, xtail = helper(cursor, i)
        prev.next = xhead

        prev = xtail
        cursor = xtail.next
        i += 1
    return head


dummy = ListNode(0)
current = dummy
for x in 'abcdefghij':
    current.next = ListNode(x)
    current = current.next

current = dummy.next
while current:
    print(f'{current.val}->', end='')
    current = current.next
print('NONE')

head = reverse(dummy.next)
current = head
while current:
    print(f'{current.val}->', end='')
    current = current.next
print('NONE')

Given below is the garbled piece of mess I came up with during the interview. The code is as is without altering anything.


class ListNode(x):
    def __init__(x):
        self.val = x
        self.next = None
        
def reverse(head):
    
    prev = None
    current = head
    
    i  = 1
    while current:
        j = 1
        start = current.next # a
        
        current2 = current #a
        prev = None
        while current2 and j <= i:
            temp = current2.next # c
            current2.next = prev # b.next -> a
            
            prev = current2 # a
            current2 = temp  # 
            j += 1
       
       start.next = prev
       current.next = temp
       i += 1
Comments (0)