Algorithm for Ordering Odds & Evens in Linked List L

[evinda]

Hello! (Wave)

Consider a singly-linked list [m] L[/m] each element of which is a struct with two fields, an integer [m]num[/m] and a pointer [m]next[/m] to the next element of the list.

Describe an algorithm that gets as argument a pointer to the first element of the list [m]L[/m] and that creates a new list [m]L'[/m] that will contain all the elements of [m]L[/m] ordered in the following way:

The elements of [m]L[/m] for which the field [m]num[/m] is an odd number have to appear in [m]L'[/m] before all the elements of which the field [m]num[/m] is an even number. The elements with an odd number at the field [m]num[/m] should keep in [m]L'[/m] the display order that they had at the initial list [m]L[/m].

The same should hold for the elements with an even number at the field [m]num[/m].

For example, if the initial list is [m]L=13->15->20->17->24->26->9->30->53->44[/m] the final list should be [m]L'=13->15->17->9->53->20->24->26->50->44[/m].That's what I have tried:

   List(L){
      if (L==NULL) return;
      node *p=NULL, *q=L, *l=L, *L3=NULL, *head2=NULL, *tail1=NULL, *tail2=NULL;
      while (q!=NULL){
            if (q-> num mod 2==1){
                if (p==NULL){
                   p->num=q->num;
                   L3=p;
                }
                else {
                   p=p->next;
                   p->num=q->num;
               }
            }
      }
      tail=p;
      while (l!=NULL){
            if (l-> num mod 2==0){
               if (l==NULL){
                   l->num=q->num;
                   head2=l;
                }
                else {
                   l=l->next;
                   l->num=q->num;
               }
            }
      }
      tail2=q;
      tail1->next=head2;
      tail1=tail2;
      return L3;
   }

Could you tell me if it is right?

 

[johng1]

Evinda,
No, it's not right. You continue to make the error of referencing a field of a null pointer. However, your main idea is okay. You traverse the list L twice with the first traversal appending all "odd" nodes to an initially empty list L3, and the second traversal appending the "even" nodes to L3. So your first while loop is pretty much correct. I could make no sense of the second while loop.
Here's a complete solution using your idea:

class Node {
public:
  int num;
  Node* next;

  Node(int v) : num(v), next(0) {
  }
};

Node* makeList(int a[], int n) {
  if (n == 0) {
    return (NULL);
  }
  int i;
  Node* first = new Node(a[0]), *p = first;
  for (i = 1; i < n; i++) {
    p->next = new Node(a[i]);
    p = p->next;
  }
  return (first);
}

Node* rearrange(Node* L) {
  Node* L3 = NULL, *p, *q;
  if (L == NULL) {
    return (NULL);
  }
  int i;
  for (i = 1; i >=0; i--) {
    q = L;
    while (q != NULL) {
      if (q->num % 2 == i) {
        if (L3 == NULL) {
          L3 = new Node(q->num);
          p = L3;
        } else {
          p->next = new Node(q->num);
          p = p->next;
        }
      }
      q = q->next;
    }
  }
  return(L3);
}

int main(int argc, char** argv) {
  int a[] = {13, 15, 20, 17, 24, 26, 9, 30, 53, 44};
  Node *L = makeList(a, 10), *p = L;
  while (p != NULL) {
    cout << p->num << " ";
    p = p->next;
  }
  cout << endl;
  Node* Lprime = rearrange(L);
  p = Lprime;
  while (p != NULL) {
    cout << p->num << " ";
    p = p->next;
  }
  cout << endl;
  return (0);
}

However, I strongly suspect the exercise meant for you to write a function that traverses the original list only once. This is only slightly more complicated. I advise you to write this function.

 

[evinda]

Evinda,
No, it's not right. You continue to make the error of referencing a field of a null pointer. However, your main idea is okay. You traverse the list L twice with the first traversal appending all "odd" nodes to an initially empty list L3, and the second traversal appending the "even" nodes to L3. So your first while loop is pretty much correct. I could make no sense of the second while loop.
Here's a complete solution using your idea:

class Node {
public:
  int num;
  Node* next;

  Node(int v) : num(v), next(0) {
  }
};

Node* makeList(int a[], int n) {
  if (n == 0) {
    return (NULL);
  }
  int i;
  Node* first = new Node(a[0]), *p = first;
  for (i = 1; i < n; i++) {
    p->next = new Node(a[i]);
    p = p->next;
  }
  return (first);
}

Node* rearrange(Node* L) {
  Node* L3 = NULL, *p, *q;
  if (L == NULL) {
    return (NULL);
  }
  int i;
  for (i = 1; i >=0; i--) {
    q = L;
    while (q != NULL) {
      if (q->num % 2 == i) {
        if (L3 == NULL) {
          L3 = new Node(q->num);
          p = L3;
        } else {
          p->next = new Node(q->num);
          p = p->next;
        }
      }
      q = q->next;
    }
  }
  return(L3);
}

int main(int argc, char** argv) {
  int a[] = {13, 15, 20, 17, 24, 26, 9, 30, 53, 44};
  Node *L = makeList(a, 10), *p = L;
  while (p != NULL) {
    cout << p->num << " ";
    p = p->next;
  }
  cout << endl;
  Node* Lprime = rearrange(L);
  p = Lprime;
  while (p != NULL) {
    cout << p->num << " ";
    p = p->next;
  }
  cout << endl;
  return (0);
}

However, I strongly suspect the exercise meant for you to write a function that traverses the original list only once. This is only slightly more complicated. I advise you to write this function.

With the function [m] rearrange [/m] we only append all "odd" nodes to the list L3, right?