Geek asks and answers

Linked List Reverse Idea

Something was listening to me, since I heard that a lot was asked in the interview. Separate reverse list. The thing is, I checked the implementations, and I was wondering if the idea I was thinking about could be applied

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

This structure is the initial condition for a linked list. I thought when we would like to reverse, right.

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

So in a loop that will take O (n) runtime , just changing the data of Node # 1 to Node # 5 , will Node # 2 with Node # 4 do the job?

+3
source share
7
   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;
 }
+4

, Node 5 . , "" . O (1) tail node, Node 5 Node 4 O (N), Node 1, Node 4.

, . , , O (N). ( , , , Node, , .)

+3

insert_head . , . , .

: , . insert_at_tail, .

, O(1). , , O(n) node ( , node ), , , O(n^2).

+3

, , , , . . , LL ( LL.addToHead(el) ).

O (n) O (1) :

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;
}

, , , - O (n ^ 2)

+2

O(n), O(n). .

+1

, . , :

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

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

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

It is not recommended to simply drop data from nodes based on their positions at the end of the output for two reasons:

  • This is not an acceptable solution if the list is large.
  • The time in visiting sites is arbitrarily longer. The approach will take longer 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  
  }
}
+1
source

More articles:


All Articles