Flatten a recursive Linked List in Objective-C

Given a linked list, where each node’s value can itself be a linked list (a recursive linked list), write a function that flattens it. Final code at Github

Pretty difficult coding questions. First I tried a recursive solution that for some reason wasn’t working for all cases and then I came up with this one.

First of all let’s declare our Node Class with properties data – can have nil or another linked list, next – pointer to a next node and name – for debugging purposes.

@interface LLNode : NSObject;

@property id data;
@property LLNode *next;
@property NSString *name;

@end

@implementation LLNode

-(instancetype)initWithName:(NSString*)name{
    self = [super init];
    if(self)
    {
        self.name = name;
    }
    return self;
}

We will have a helper function that takes in a node and insert it’s data Linked list after it.

-(void)insertListAfterNode:(LLNode*)node{
    if (!node.data)
        return;
    else{
        LLNode *tempNext = node.next;
        node.next = node.data;
        node.data = nil;
        while (node.next)
            node = node.next;
        node.next = tempNext;
    }
}

And the final function is to go through the linked list and insert all child linked lists in a row.

-(void)processLinkedList:(LLNode*)root{
    LLNode *pointer = root;
    while (pointer.next) {
         [self insertListAfterNode:pointer];
        pointer = pointer.next;
    }
}

At the end we should have linked list flattened.

Objective-C