CareerCup

Here's a hash based solution for this problem.
Create a structure

struct node
{
    int* address;
    bool visited;
    struct node* next;
};

1. Create an array of 26 (alphabatic characters) node.
2. For each entry in linked list fill the hash table (based on starting character).
2.1. address - pointer to for linked list node.
2.2. visited = false
2.3. next = NULL (it will come into use when two nodes have same starting character, using the idea of chaining concept in hashing)

Now lets try to fill the given linked list in hash table:-
Pointer Value :- 0x100 0x200 0x300 0x400 0x500 0x600 0x700
Linked List :- here -> is -> ew -> long -> shut -> error -> roll

Once these pointer values are feeded into the nodes we are done with the hash table.

Now, to find the possibilities we start from first node of linked list. Let's do it one by one.

1. a. Here (search for h in hash table).
b. Since 'e' is last character of here, now search hash table for 'e'. Now we have two enteries for 'e' we will do it one at a time. Lets say we choose "ew" first time, and if we have next of "ew" != NULL, we mark "ew" as visited (i.e. "ew"->visited = true) now we proceed for 'w' and continue same ways.
c. Since after here 'e', there is one more possibility of having "error" 'e', for "ew" we have already visited (since visited flag for "ew" is true), we will go forward in that chain and continue.

In this way we can have all possiblities. Thanx

We can create a directed graph here . Each node of graph will be a word and we make a edge from node to another if the end of word of first node is start of word of another node (eg we can make an edge from "here" to "ew" and "here" to "error") . After our graph is built all we need is to do DFS from each node and print all paths.

first we should check how to handle circle like ab->ba.
here I use a set to detect circle and only save {ab, ba}.
connect the last node to the root, then we can use a recursive function to handle all nodes.

class SListNode {
public:
  string v;
  SListNode *next;
  SListNode(string s) : v(s), next(NULL) {};
};
vector<vector<string>> line(SListNode *root, vector<string> &pre, set<string> &predic) {
  vector<vector<string>> res;
  string &tmp = root->v;
  pre.push_back(root->v);
  predic.insert(root->v);
  SListNode *p = root->next;
  while (p != root) {
    if (p->v[0] == tmp.back() && predic.find(p->v) == predic.end()) {
      auto tmpres = line(p, pre, predic);
      res.insert(res.end(), tmpres.begin(), tmpres.end());
    }
    p = p->next;
  }
  if (res.empty()) {
    res.push_back(pre);
  }
  predic.erase(root->v);
  pre.pop_back();
  return res;
}

vector<vector<string>> line(SListNode *root) {
  if (!root) return vector<vector<string>>();
  SListNode *p = root;
  while (p->next) p = p->next;
  p->next = root;
  vector<string> tmp;
  set<string> tmpdic;
  auto res = line(root, tmp, tmpdic);
  p->next = NULL;
  return res;
}

sample result:

Here    ew
Here    error   roll    long

another test case: ab->ba->acd->bcd
result:

ab      ba      acd
ab      bcd

Algorithms steps
1) create trie of the string given in the linked list.
2) start from first node, if found first child with end char, consider that, then go unto to the point where either the string ends or it convert into to children, if you see such case, put them into the stack, and as you travel in the trie, mark the string in the list as travelled, so that when one choose next string from list, we always choose untravelled string.
3) try until the stack is empty.

In the stack you will insert the start and end node of the sequences

Complexity : O(N) time + space used by trie.