Student Interview Question
fresherssCountry: United States
/*
Note:
- it's a linked list, not double linked
- the list is altered, so, one should do it in place
- best conceivable runtime is O(n)
Solution in O(N) runtime and O(1) space
1) step through the list to determine the size
2) invert 2nd half of the list
3) shuffle together
*/
#include <iostream>
struct Item
{
Item* next_;
int value_;
Item(int value, Item* next)
: next_(next), value_(value) { }
};
size_t getSize(Item* item);
Item* getKthItem(Item* item, size_t k);
Item* invertList(Item* item);
void printList(Item* item);
void shuffleList(Item* item)
{
size_t n = getSize(item);
if(n <= 2) return;
Item* lastFirstHalf = getKthItem(item, n / 2 - 1);
Item* lastSeconHalf = lastFirstHalf->next_;
Item* secondHalf = invertList(lastSeconHalf);
Item* firstHalf = item;
lastFirstHalf->next_ = nullptr;
while(firstHalf != nullptr) {
Item* current = firstHalf;
firstHalf = firstHalf->next_;
current->next_ = secondHalf;
secondHalf = secondHalf->next_;
current->next_->next_ = firstHalf;
}
}
int main()
{
Item *list = new Item(1,
new Item(2,
new Item(3,
new Item(4,
new Item(5,
new Item(6, nullptr))))));
shuffleList(list);
printList(list);
}
Item* invertList(Item* item)
{
Item* prev = nullptr;
Item* next = nullptr;
while(item != nullptr) {
next = item->next_;
item->next_ = prev;
prev = item;
item = next;
}
return prev;
}
Item* getKthItem(Item* item, size_t k) {
while(k > 0 && item != nullptr) {
item = item->next_;
k--;
}
return item;
}
size_t getSize(Item* item) {
size_t size = 0;
while(item != nullptr) {
item = item->next_;
size++;
}
return size;
}
void printList(Item* item)
{
while(item != nullptr) {
std::cout << item->value_ << " ";
item = item->next_;
}
}
- PR December 04, 2016