Member Avatar for brian63304

I am trying to create a list of nodes and then put numbers in them.. I can do that. But I need help trying to sort the nodes. Here is my program.

Thank you,
Brian

int null = -1;
typedef struct Node { 
   int val;
   Node next;
   Node(int v, Node t){
        val = v;
        next = t;
        }//node    
} Node;

Node sort(Node a);

int main() {
   Node a = new Node(0, null); 
   
   for(int i=1;i<=10;i++) {                
      Node b = new Node(0, null);             //create b node
      b.val = rand();                 //fill b node with random numbers
      b.back  = a;
      a = b;
   }
   Node m = sort(a);            //sort nodes pass to m node
   while(m) {
      cout << m.val << " ";      //print out nodes      
      m = m.next ;
   }
   return 0;
}

Node sort(Node a){                       //sorts nodes
    Node  b = new Node(0, null);
    Node  x, u, t;
    
    while(a.next != null){
       t = a.next;
       u = t.next;
       a.next = u;
       for(x = a; x.next != null; x = x.next)
          if(x->next.val > t.val) break;
       t.next = x.next; x.next = t; 
   }      
   return b;
}// sort
  • 3 Contributors
  • 2 Replies
  • 87 Views
  • 23 Hours Discussion Span
  • Latest Post Latest Post by kafkanien

Dani AI

Generated

This thread shows a few common mistakes when implementing a singly linked list and an in-place sort. was correct to point out the structural problem: the node should hold a pointer to the next node, not an instance. The original code also mixes an integer sentinel with pointer logic, uses inconsistent member names, and returns the wrong head from the sort routine. Below is a minimal, safe pattern that fixes those issues and performs an insertion-style sort in-place.

struct Node {
    int val;
    Node* next;
    Node(int v=0, Node* n=nullptr) : val(v), next(n) {}
};

Node* insertion_sort(Node* head) {
    Node* sorted = nullptr;
    while (head) {
        Node* cur = head;
        head = head->next;
        if (!sorted || cur->val <= sorted->val) {
            cur->next = sorted;
            sorted = cur;
        } else {
            Node* p = sorted;
            while (p->next && p->next->val < cur->val) p = p->next;
            cur->next = p->next;
            p->next = cur;
        }
    }
    return sorted;
}

Build the list by prepending with new Node(rand(), head), call insertion_sort, then traverse with for(Node* p = head; p; p = p->next). This algorithm is O(n^2) but simple and pointer-safe. For production code prefer STL containers or modern smart pointers to avoid manual new/delete. Also ignore the unrelated post by . For modern compilers, prefer nullptr over integer sentinels (see nullptr).

Recommended Answers

All 2 Replies

Member Avatar for Dave Sinkula

A struct cannot contain an instance of itself -- perhaps you meant to have a pointer to the next instance in the Node (and elsewhere).

Member Avatar for kafkanien

rtsp://

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.