Structure de données - liste chaînée.
Dans ce blog, je fournirai quelques questions sur la liste liée, ce qui m'a personnellement aidé à me familiariser avec. Avoir des connaissances préalables sur STL, Linked List et Recursion vous aidera à comprendre encore plus ce blog axé sur la résolution de problèmes.
Personnellement, je crois que la liste liée est l'une des structures de données les plus simples. Mais il faut construire la logique et la capacité de la visualiser pour faire face à des situations délicates ou difficiles la concernant.
J'ai choisi des questions de la plateforme LeetCode, qui est l'une des meilleures plateformes pour résoudre des problèmes et rencontrer des problèmes algorithmiques. Je n'ai pas couvert les choses de base car il existe déjà de nombreuses ressources sur Internet pour cela. Ce blog est davantage destiné à la résolution de problèmes et à la fourniture de questions importantes sur la liste liée. J'ai également fourni le code pour quelques-uns d'entre eux en langage de programmation C++.
LISTE LIÉE
Je passerai rapidement en revue certains points qu'il faut garder à l'esprit en pensant à une liste chaînée en général. Tout d'abord, il faut savoir qu'une liste chaînée est une structure de données linéaire. Ici, les éléments ne sont pas stockés à des emplacements de mémoire contigus, contrairement à un tableau. Dans une liste liée, les éléments sont connectés les uns aux autres à l'aide de pointeurs, ce qui nous donne la possibilité d'ajouter, de supprimer ou d'insérer des éléments dans une liste liée. Il n'est pas nécessaire d'initialiser la taille d'une liste chaînée, alors que, comme dans un tableau, c'est une nécessité. Il est difficile d'accéder directement à un élément dans une liste liée car il faut parcourir la liste liée pour atteindre cet élément, contrairement à un tableau où l'on peut accéder à n'importe quel élément à l'aide d'un index.
AIGUILLE
Un pointeur est une variable qui stocke l'adresse mémoire comme sa valeur.
Prenons maintenant quelques exemples pour comprendre ce qu'est le pointeur :
int *ptr = &var; // assignation de l'adresse de la variable var au pointeur ptr.
car*ptr = &var; // assignation de l'adresse de la variable var au pointeur ptr.
int*ptr ; // 'ptr' est un pointeur pointant vers une valeur parasite.
Maintenant, je vais fournir certaines des questions LeetCode, qu'une personne devrait certainement résoudre pour construire une logique et faire face à des situations délicates.
La plupart du temps, on peut résoudre les questions de la majorité impliquant une liste chaînée en utilisant l'approche des pointeurs rapides et lents et l'inversion en place d'une liste chaînée.
PROBLÈMES
- Pointeurs rapides et lents.
ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while(fast && fast -> next)
slow = slow -> next
fast = fast -> next -> next;
return slow;
}
bool isPalindrome(ListNode* head) {
ListNode *slow = head, *fast = head, *prev, *temp;
while(fast && fast -> next)
slow = slow -> next, fast = fast -> next -> next;
prev = slow, slow = slow -> next, prev-> next = NULL;
while(slow)
temp = slow -> next, slow -> next = prev, prev = slow, slow = temp;
fast = head, slow = prev;
while(slow)
if(fast -> val != slow -> val) return false;
else fast = fast -> next, slow = slow -> next;
return true;
}
bool hasCycle(ListNode *head) {
if(head == NULL) return false;
ListNode *fast = head;
ListNode *slow = head;
while(fast != NULL and fast -> next != NULL) {
fast = fast -> next -> next;
slow = slow -> next;
if(fast == slow) return true;
}
return false;
}
ListNode *detectCycle(ListNode *head) {
if(head == NULL || head -> next == NULL) return NULL;
ListNode *slow = head;
ListNode *fast = head;
ListNode *cycleStart = head;
while(fast -> next and fast -> next -> next) {
slow = slow -> next;
fast = fast -> next -> next;
if(slow == fast) {
while(slow != cycleStart) {
slow = slow -> next;
cycleStart = cycleStart -> next;
}
return cycleStart;
}
}
return NULL;
}
ListNode* removeElements(ListNode* head, int val) {
if(head == nullptr) return head;
while(head != nullptr && head -> val == val) {
head = head -> next;
}
ListNode* curr = head;
while(curr != nullptr and curr -> next != nullptr) {
if(curr -> next -> val == val) {
curr -> next = curr -> next -> next;
}
else
curr = curr -> next;
}
return head;
}
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
if(!list1 || list2 && list1 -> val > list2 -> val)
swap(list1, list2);
if(list1)
list1 -> next = mergeTwoLists(list1 -> next, list2);
return list1;
}
un. Liste chaînée inversée 1
ListNode* reverseList(ListNode* head) {
ListNode* nextNode;
ListNode* prevNode = NULL;
while(head) {
nextNode = head -> next;
head -> next = prevNode;
prevNode = head;
head = nextNode;
}
return prevNode;
}
Vous devriez essayer par vous-même. C'est l'extension du problème ci-dessus.
c. Échanger des nœuds dans une liste chaînée
ListNode* swapNodes(ListNode* head, int k) {
ListNode* temp = head;
int cnt = 0;
while(temp) {
cnt++;
temp = temp -> next;
}
ListNode *start = head, *end = head;
int s = k - 1, e = cnt - k;
for(int i = 0; i < s; i++)
start = start -> next;
for(int i = 0; i < e; i++)
end = end -> next;
swap(start -> val, end -> val);
return head;
}
void reorderList(ListNode* head) {
if((!head) || (!head -> next) || (!head -> next -> next)) return;//Edge Cases
stack<ListNode*> st;
ListNode* temp = head;
int size = 0;
while(temp != NULL) {
st.push(temp);
size++;
temp = temp -> next;
}
ListNode* ptr = head;
for(int j = 0; j < size/2; j++)//Between every two nodes insert the one in the top of the stack
{
ListNode* element = st.top();
st.pop();
element -> next = ptr -> next;
ptr -> next = element;
ptr = ptr -> next -> next;
}
ptr -> next = NULL;
}
ListNode* swapPairs(ListNode* head) {
if(head == nullptr || head -> next == nullptr) return head;
ListNode* dummy = new ListNode();
ListNode* prev = dummy;
ListNode* curr = head;
while(curr and curr -> next) {
prev -> next = curr -> next;
curr -> next = prev -> next -> next;
prev -> next -> next = curr;
prev = curr;
curr = curr -> next;
}
return dummy -> next;
}
ListNode* reverseEvenLengthGroups(ListNode* head) {
if(!head ) return head;
ListNode* curr = head, *p;
int sz = 1;
while(curr) {
p = curr;
vector<int> vec;
for(int i = 0 ;i < sz && curr != NULL ; i++) {
vec.push_back(curr -> val);
curr = curr -> next;
}
if(vec.size() % 2 == 0) {
reverse(vec.begin(), vec.end());
for(int i = 0; i < vec.size(); i++){
p -> val = vec[i];
p = p -> next;
}
}
sz++;
}
return head;
}
Essayez-les vous-même d'abord pour une meilleure compréhension.
un. Aplatir l'arborescence binaire en liste chaînée
void flatten(TreeNode* root) {
if(root == NULL) return;
flatten(root -> left);
flatten(root -> right);
if(root -> left) {
TreeNode* right = root -> right;
root -> right = root -> left;
root -> left = NULL;
while(root -> right)
root = root -> right;
root -> right = right;
}
}
ListNode* rotateRight(ListNode* head, int k) {
if(head == nullptr || head -> next == nullptr || k == 0)
return head;
int len = 1;
ListNode* tail = head;
while(tail -> next != nullptr) {
len++;
tail = tail -> next;
}
tail -> next = head;
k = len - k % len;
while(k) {
tail = tail -> next;
k--;
}
head = tail -> next;
tail -> next = nullptr;
return head;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(head == nullptr) return head;
ListNode* temp = new ListNode();
temp -> next = head;
ListNode* fast = temp;
ListNode* slow = temp;
for(int i = 0; i < n; i++) {
fast = fast -> next;
}
while(fast -> next != nullptr) {
fast = fast -> next;
slow = slow -> next;
}
slow -> next = slow -> next -> next;
return temp -> next;
}
ListNode* oddEvenList(ListNode* head) {
if(!head || !head -> next || !head -> next -> next)
return head;
ListNode* odd_p = head;
ListNode* even_p = head -> next;
ListNode* headofeven = even_p;
while(odd_p -> next && even_p -> next) {
odd_p -> next = odd_p -> next -> next;
even_p -> next = even_p -> next -> next;
odd_p = odd_p -> next;
even_p = even_p -> next;
}
odd_p -> next = headofeven;
return head;
}
Node* connect(Node* root) {
if(root == NULL) return NULL;
//connects the left subtree of same level with right subtree of that same level
if(root -> left != NULL)
root -> left -> next = root -> right;
//connect the rightmost node of a level to the leftmost node of the next level.
if(root -> right != NULL && root -> next != NULL)
root -> right -> next = root -> next -> left;
//recursive calls for left and right subtrees.
connect(root -> left);
connect(root -> right);
return root;
}
Vous devriez résoudre ces questions, une fois que vous êtes confiant dans les problèmes de liste chaînée. Ces questions mettront à l'épreuve votre compréhension de divers concepts en profondeur.
un. Fusionner k listes triées
b. Nœuds inversés dans les groupes k
c. Cache LFU
DE CONCLURE
J'ai fourni certains des meilleurs problèmes de LeetCode, qui vous aideront à vous familiariser avec la liste liée. Vous devriez toujours visiter la section de discussion de LeetCode, même si vous avez résolu la question par vous-même. Comme vous apprendrez à connaître différents codes et approches pour résoudre les questions qui sont très utiles pour un programmeur.
Après les avoir résolus, vous aurez certainement l'intuition de résoudre tout nouveau problème que vous pourriez rencontrer lors d'un concours ou d'un concours de codage. Ce sont également parmi les questions qui sont posées à plusieurs reprises dans les entretiens.
J'ai essayé de consolider certaines questions importantes sur la liste liée via ce blog. J'ai fait des recherches approfondies sur la liste liée sur plusieurs plates-formes tout en l'étudiant et j'ai trouvé ces questions les plus utiles. Connaître ces questions vous donnera certainement un avantage sur les autres.
Toute suggestion ou critique constructive est la bienvenue. À travers ce blog, je révise également mes concepts de structures de données et d'algorithmes et j'essaie de contribuer à la communauté, ce qui m'a aidé à l'apprendre en premier lieu.
![Qu'est-ce qu'une liste liée, de toute façon? [Partie 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
