В этом блоге я буду задавать вопросы о Linked List, которые лично помогли мне освоиться с ним. Наличие предварительных знаний о STL, связанных списках и рекурсии поможет вам лучше понять этот блог, ориентированный на решение проблем.
Я считаю, что связанный список — одна из самых простых структур данных. Но нужно построить логику и способность визуализировать ее, чтобы решать сложные или сложные ситуации, связанные с ней.
Я выбрал вопросы с платформы LeetCode, которая является одной из лучших платформ для решения проблем и решения алгоритмических проблем. Я не рассмотрел основы, так как в Интернете уже есть много ресурсов для этого. Этот блог больше ориентирован на решение проблем и предоставление важных вопросов по связанному списку. Я также предоставил код для некоторых из них на языке программирования C++.
СВЯЗАННЫЙ СПИСОК
Я быстро пройдусь по некоторым моментам, которые необходимо иметь в виду, думая о связанном списке в целом. Во-первых, нужно знать, что связанный список — это линейная структура данных. Здесь элементы не хранятся в смежных ячейках памяти, в отличие от массива. В связанном списке элементы связаны друг с другом с помощью указателей, что дает нам возможность добавлять, удалять или вставлять элементы в связанный список. Нет необходимости инициализировать размер связанного списка, где, как и в массиве, это необходимо. Трудно получить доступ к элементу напрямую в связанном списке, поскольку для достижения этого элемента необходимо пройти по связанному списку, в отличие от массива, где мы можем получить доступ к любому элементу с помощью индекса.
УКАЗАТЕЛЬ
Указатель — это переменная, которая хранит адрес памяти в качестве своего значения.
Теперь возьмем несколько примеров, чтобы понять, что такое указатель:
int *ptr = // присвоение адреса переменной var указателю ptr.
char*ptr = // присвоение адреса переменной var указателю ptr.
интервал*указатель; // ‘ptr’ — это указатель, указывающий на какое-то мусорное значение.
Теперь я предоставлю некоторые вопросы LeetCode, которые человек обязательно должен решить, чтобы выстроить логику и справиться со сложными ситуациями.
В основном можно решить большинство вопросов, связанных со связанным списком, используя подход «Быстрые и медленные указатели» и «Обратное обращение связанного списка на месте».
ПРОБЛЕМЫ
- Быстрые и медленные указатели.
а. Середина связанного списка
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;
}
в. Цикл связанного списка 1
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;
}
д. Цикл связанного списка 2 (расширение цикла 1 связанного списка)
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;
}
2. Инверсия связанного списка на месте.
а. Обратно связанный список 1
ListNode* reverseList(ListNode* head) {
ListNode* nextNode;
ListNode* prevNode = NULL;
while(head) {
nextNode = head -> next;
head -> next = prevNode;
prevNode = head;
head = nextNode;
}
return prevNode;
}
б. Обратно связанный список 2
Вы должны попробовать это самостоятельно. Это расширение вышеуказанной проблемы.
в. Перестановка узлов в связанном списке
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;
}
3. Несколько важных вопросов для практики.
Сначала попробуйте их сами, чтобы лучше понять.
а. Свести двоичное дерево к связанному списку
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;
}
в. Удалить N-й узел из конца списка
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;
}
4. Несколько сложных, но очень важных вопросов. Неоднократно спрашивали на собеседованиях.
Вы должны решить эти вопросы, когда будете уверены в проблемах со связанными списками. Эти вопросы бросят вызов вашему глубокому пониманию различных концепций.
а. Объединить k отсортированные списки
б. Обратные узлы в k-группах
в. LFU-кэш
ЗАКЛЮЧЕНИЕ
Я предоставил некоторые из лучших задач LeetCode, которые помогут вам освоиться со связанным списком. Вы всегда должны посещать раздел обсуждения LeetCode, даже если вы решили вопрос самостоятельно. Так как вы узнаете о разном коде и подходах к решению вопросов, которые очень полезны для программиста.
После их решения у вас определенно появится интуиция для решения любой новой проблемы, с которой вы можете столкнуться в конкурсе или любом соревновании по программированию. Эти вопросы также входят в число вопросов, которые неоднократно задают в интервью.
Я попытался объединить некоторые важные вопросы о Linked List в этом блоге. Я тщательно изучил Linked List на нескольких платформах, изучая его, и нашел эти вопросы наиболее полезными. Знание этих вопросов определенно даст вам преимущество перед другими.
Любые предложения или конструктивная критика очень приветствуются. В этом блоге я также пересматриваю свои концепции структур данных и алгоритмов и пытаюсь внести свой вклад в сообщество, что в первую очередь помогло мне его изучить.
