CODEWITHSUNDEEP
performancealgorithmdata-structureslinked-list
Ali
Ali

Reputation: 5476

An Idea Related To Linked List Reversal

Something has been bugging me since I've heard it was asked a lot in the interviews. Reverse a singly linked list. The thing is that I've checked the implementations and I was wondering whether the idea I was thinking could be applied

|data1|->|data2|->|data3|->|data4|->|data5|

This structure is the initial condition of the linked list. I was thinking when we would like to reverse wouldn't it be like;

|data5|->|data4|->|data3|->|data2|->|data1|

Thus, in a loop which will take O(n) running time, simply reversing the data of Node #1 with Node #5, Node #2 with Node #4 would do the job?

Upvotes: 3

Views: 362

Answers (7)

Sachin Mhetre
Sachin Mhetre

Reputation: 4543

   typedef struct Node
   {
     char data;
     struct Node* next;
   } Node; 



    Node* reverse(Node* root)
    {
       Node* new_root = 0;
       while (root)
       {
           Node* next = root->next;
           root->next = new_root;
           new_root = root;
           root = next;
       }
       return new_root; 
    } 



int main()
{
   Node d = { 'd', 0 };
   Node c = { 'c', &d };
   Node b = { 'b', &c };
   Node a = { 'a', &b };
   Node* root = &a; 
   root = reverse(root);
   return 0;
 }

Upvotes: 4

Tejas Patil
Tejas Patil

Reputation: 6169

It is not a good idea to just reverse data from nodes based on their positions in the end output for 2 reasons:

  1. It wont be a feasible solution if the list is of large size
  2. The time in visiting nodes in arbitrary fashion is more. The approach will take more time than O(n).

Consider this pseudo code:

reverse_list(node *head) 
{
  node *temp;
  *temp = head -> next;
  head-> next = NULL;

  while (temp != NULL) {
     swap_nodes(head, temp->next);  // this aint copying data from nodes, actual nodes are 
     swap_nodes(head, temp);        // swapped based on its and parents' next pointers  
  }
}

Upvotes: 1

kasavbere
kasavbere

Reputation: 6003

when asked, the usual restriction is to reverse the list in place so that you don't use any extra space except maybe three variables or fewer. That's why the question is not trivial. Therefore, you may neither use recursion nor your own explicit stack nor another LL (where you would do LL.addToHead(el) as you walk the original).

so here is a good answer O(n) time and O(1) space: 

Node reverse(Node n){//n is head; you may also get the LL
    if(null == n || null == n.next)
       return n;
    Node a=n, b=a.next, c=b.next;
    a.next=null; b.next=a;
    while(null != c){
       a=c;
       c=c.next;
       a.next=b;
       b=a;
    }
    return b;
}

By the way, the solution you propose is O(n^2)

Upvotes: 2

wildplasser
wildplasser

Reputation: 44250

The idea will fail miserably if the list is heterogenous, or the nodes are unequal in size. Take for example:

struct base {
   int type;
   struct base *next;
   };

struct small {
   struct base common;
   int value;
   };

struct big {
    struct base common;
    char payload[12345];
    };

Upvotes: 1

Charles Salvia
Charles Salvia

Reputation: 53319

Your algorithm requires that we start at Node 5, and work backwards from there. But it's a singly linked list - meaning we don't have "back" pointers. Even if we have O(1) access to a tail node, getting from Node 5 to Node 4 would be an O(N) operation in itself, since we need to start again from Node 1 in order to reach Node 4.

So, it's not a good algorithm for a singly-linked list. For a doubly-linked list, where we have access to back pointers, it would give us O(N) complexity. (Your algorithm is also not entirely type-agnostic, since it requires that the data stored in each node is copyable or moveable so we can swap it.)

Upvotes: 3

UmNyobe
UmNyobe

Reputation: 22910

There is an O(n) solution which use O(n) space. Think about evading the issue of accessing element in linear time.

Upvotes: 1

jason
jason

Reputation: 241701

You want to write a method insert_head and repeatedly use it. So you walk from the head of your original list, and append to the head of a new linked list. Thus, the tail of your original list becomes the head of the new list.

Here's another way to do this: walk your original list, pushing the nodes onto a stack. Then, pop and insert_at_tail as you go into a new list.

Your algorithm fails because you can't walk backwards in a singly linked list in O(1) time. To do as you suggest, it's O(n) per node (you head to walk all the way from the head to where you are to get the previous node each time), and thus to reverse the whole list is O(n^2).

Upvotes: 3

Related Questions