Mastering linked Lists

Linked List pointers
Classic problems
- Reverse
- Split

Dans l’exercice IsSorted, on vous demande d’écrire une fonction isSorted qui reçoit un pointeur sur une noeud d’une liste qui représente le head d’une liste chainée. Votre fonction doit renvoyer un booléen qui indique si cette liste chainée est triée ou non.

struct ListNode {
    int data;            //valeur dans chaque noeud
    ListNode *next;      // pointeur sur le noeud suivant
}

DoubleIt

Dans l’exercice doubleIt, on vous demande d’écrire une fonction doubleList qui reçoit un pointeur sur le head d’une liste chainée et qui ajoute une copie de cette chaine a la fin de celle ci.

Par exemple si la chaine est

{ 1, 35, 28, 7}

alors l’appel doubleList(front) modifiera la liste en:

{ 1, 35, 28, 7, 1 , 35, 28, 7}

Contraintes

Vous ne pouvez pas utiliser des structure de donnes comme un vecteur ou un string.
Au maximum vous devez créer \(N\) noeuds u \(N\) est le nombre de neouds de la liste originale.

Expand

Dans l’exercice expand, on vous demande d’écrire une fonction expand qui reçoit une référence sur un pointeur ListNode représentant la début d’une liste chainée et un paramètre \(k\). Cette fonction doit remplacer chaque noeud par \(k\) copies avec une valeur \(\dfrac{v}{k}\).

Par exemple, supposons que la liste initiale est

{12, 34, -8, 3, 46}

l’appel expand(L, 2) changera la liste en

{6, 6, 17, 17, -4, -4, 1. 1, 23, 23}

Si par exemple, on avait execute expand(L, 3), on aura alors:

{4, 4, 4, 11, 11, 11, -2, -2, -2, 1, 1, 1, 15, 15, 15}

Si une liste est vide, elle restera vide.
Si \(k\) est négatif, lancer une exception.
Si \(k=0\), détruire toute la chaine.

{8, 7, -4, 19, 0, 43, -8, -7, 2}

Apres l’appel, la liste deviendra

{-7, -8, -4, 8, 7, 19, 0, 43, 2}

Remarquer que les nombres positifs garde leur ordre d’apparition.
Contrairement, l’ordre d’apparition des nombres négatifs est inverse.

Linked List pointers

Is Sorted

DoubleIt

Expand

Classic problems

Reverse

Split