Struktur Data - Daftar Tertaut.
Di blog ini saya akan memberikan beberapa pertanyaan tentang Linked List, yang secara pribadi membantu saya untuk merasa nyaman dengannya. Memiliki pengetahuan prasyarat tentang STL, Daftar Tertaut, dan Rekursi akan membantu Anda lebih memahami blog yang berfokus pada pemecahan masalah ini.
Secara pribadi, saya percaya bahwa Daftar Tertaut adalah salah satu struktur data yang paling sederhana. Tetapi seseorang harus membangun logika dan kemampuan untuk memvisualisasikannya untuk mengatasi situasi rumit atau sulit terkait hal itu.
Saya telah memilih pertanyaan dari platform LeetCode, yang merupakan salah satu platform terbaik untuk pemecahan masalah dan menghadapi masalah algoritmik. Saya belum membahas hal-hal dari dasar karena sudah ada banyak sumber daya di internet untuk itu. Blog ini lebih untuk pemecahan masalah dan memberikan pertanyaan-pertanyaan penting tentang Linked List. Saya juga telah menyediakan kode untuk beberapa di antaranya dalam bahasa pemrograman C++.
DAFTAR TERKAIT
Saya akan segera membahas beberapa poin yang harus diingat saat memikirkan Daftar Tertaut secara umum. Pertama, kita harus tahu bahwa Daftar Tertaut adalah struktur data linier. Di sini elemen tidak disimpan di lokasi memori yang berdekatan, tidak seperti di Array. Dalam Daftar Tertaut, elemen-elemen terhubung satu sama lain dengan bantuan pointer, yang memberi kita fleksibilitas untuk menambah, menghapus, atau menyisipkan elemen dalam Daftar Tertaut. Tidak perlu untuk menginisialisasi ukuran Daftar Tertaut, sedangkan dalam Array itu adalah suatu keharusan. Sulit untuk mengakses elemen secara langsung dalam Daftar Tertaut karena seseorang harus melintasi Daftar Tertaut untuk mencapai elemen itu, tidak seperti di Array di mana kita dapat mengakses elemen apa pun dengan bantuan indeks.
PENUNJUK
Pointer adalah variabel yang menyimpan alamat memori sebagai nilainya.
Sekarang ambil beberapa contoh untuk memahami apa itu pointer:
int *ptr = &var; // menugaskan alamat variabel var ke penunjuk ptr.
char*ptr = &var; // menugaskan alamat variabel var ke penunjuk ptr.
int*ptr; // 'ptr' adalah pointer yang menunjuk ke beberapa nilai sampah.
Sekarang saya akan memberikan beberapa pertanyaan LeetCode, yang harus dipecahkan seseorang untuk membangun logika dan mengatasi situasi sulit.
Sebagian besar orang dapat menyelesaikan sebagian besar pertanyaan yang melibatkan Daftar Tertaut menggunakan pendekatan Penunjuk Cepat dan Lambat dan Pembalikan Di Tempat dari Daftar Tertaut.
MASALAH
- Pointer Cepat dan Lambat.
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;
}
A. Daftar Tertaut Terbalik 1
ListNode* reverseList(ListNode* head) {
ListNode* nextNode;
ListNode* prevNode = NULL;
while(head) {
nextNode = head -> next;
head -> next = prevNode;
prevNode = head;
head = nextNode;
}
return prevNode;
}
Anda harus mencobanya sendiri. Ini adalah perpanjangan dari masalah yang diberikan di atas.
C. Menukar node dalam Daftar Tertaut
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;
}
Cobalah sendiri terlebih dahulu untuk pemahaman yang lebih baik.
A. Ratakan Pohon Biner ke Daftar Tertaut
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;
}
Anda harus menyelesaikan pertanyaan-pertanyaan ini, setelah Anda yakin dengan soal-soal Linked List. Pertanyaan-pertanyaan ini akan menantang pemahaman Anda tentang berbagai konsep secara mendalam.
A. Menggabungkan k Daftar yang Diurutkan
B. Membalikkan Node di k-Group
C. Cache LFU
UNTUK MENYIMPULKAN
Saya telah memberikan beberapa masalah LeetCode terbaik, yang akan membantu Anda merasa nyaman dengan Linked List. Anda harus selalu mengunjungi bagian diskusi LeetCode, bahkan jika Anda telah menyelesaikan pertanyaan Anda sendiri. Seperti yang akan Anda ketahui tentang berbagai kode dan pendekatan untuk menyelesaikan pertanyaan yang sangat membantu bagi seorang programmer.
Setelah menyelesaikan ini, Anda pasti akan mendapatkan intuisi untuk menyelesaikan masalah baru yang mungkin Anda temui dalam Kontes atau Kompetisi Coding apa pun. Ini juga di antara pertanyaan yang berulang kali ditanyakan dalam Wawancara.
Saya telah mencoba menggabungkan beberapa pertanyaan penting tentang Linked List melalui blog ini. Saya telah meneliti secara ekstensif tentang Daftar Tertaut di berbagai platform sambil mempelajarinya dan menemukan pertanyaan ini paling membantu. Mengetahui tentang pertanyaan-pertanyaan ini pasti akan memberi Anda keunggulan dibandingkan orang lain.
Setiap saran atau kritik yang membangun sangat diharapkan. Melalui blog ini saya juga merevisi konsep Struktur Data dan Algoritma saya dan mencoba berkontribusi kepada komunitas, yang membantu saya mempelajarinya sejak awal.
![Apa itu Linked List? [Bagian 1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
