Three tiny puzzles:
- Given the following interface:
interface INode{INode Next { get; set; }object Data { get; }}
and a reference to root INode root reverse a one-linked list. Do not use any additional collections, as arrays, lists or stacks. - The same for this interface:
interface INode{INode Next { get; }object Data { get; set; }} - And the same for this:
interface INode{INode Next { get; }object Data { get; }}
Are there any complexity constraints?
ReplyDeleteIdeally, O(1) :). But O(N) will be cool too. For memory, I'm not sure, whether all puzzles could be solved within O(1).
DeleteShould resulting linked list be also in canoncal form, i.e. the head item? If so, can one introduce an alternative implementation to #3? Otherwise, how can immutable interface be reversed?
ReplyDeleteIn other words, can helper INode objects (not collections!) be used to solve #3? Should the resulting list contain exactly the same INode instances or just Data order needs to be reversed?
> Should resulting linked list be also in canoncal form, i.e. the head item?
DeleteYes.
> If so, can one introduce an alternative implementation to #3? Otherwise, how can immutable interface be reversed? In other words, can helper INode objects (not collections!) be used to solve #3? Should the resulting list contain exactly the same INode instances or just Data order needs to be reversed?
You need to satisfy the INode contract only.
Simple recursive solution:
Deletehttp://pastebin.com/yYPy5yVk
Yes, fine enough. :)
Delete