データ構造 - リンクされたリスト。
このブログでは、個人的に慣れるのに役立ったリンク リストに関するいくつかの質問を紹介します。STL、リンクリスト、再帰に関する前提知識があると、この問題解決に焦点を当てたブログをさらに理解するのに役立ちます。
個人的には、リンク リストは最も単純なデータ構造の 1 つであると考えています。しかし、それに関する厄介な状況や困難な状況に対処するには、ロジックとそれを視覚化する能力を構築する必要があります。
私は LeetCode プラットフォームから質問を選択しました。これは、問題を解決し、アルゴリズムの問題に遭遇するための最良のプラットフォームの 1 つです。インターネット上にはすでに多くのリソースがあるため、基本的なことからは説明しませんでした。このブログは、問題解決とリンク リストに関する重要な質問を提供することを目的としています。そのうちのいくつかについては、C++ プログラミング言語でコードも提供しました。
リンクされたリスト
リンク リスト一般について考えるときに留意しなければならない点をいくつか簡単に説明します。まず、リンク リストは線形データ構造であることを知っておく必要があります。ここでは、配列とは異なり、要素は連続したメモリ位置に格納されません。リンク リストでは、要素はポインタを使用して相互に接続されているため、リンク リスト内の要素を柔軟に追加、削除、または挿入できます。配列の場合と同様に、リンク リストのサイズを初期化する必要はありません。インデックスを使用して任意の要素にアクセスできる配列とは異なり、リンク リスト内の要素に直接アクセスすることは困難です。その要素に到達するにはリンク リストを横断する必要があります。
ポインタ
ポインタは、メモリアドレスを値として格納する変数です。
ポインタとは何かを理解するために、いくつかの例を示します。
int *ptr = &var; // 変数 var のアドレスを ptr ポインタに代入します。
char*ptr = &var; // 変数 var のアドレスを ptr ポインタに代入します。
int*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;
}
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;
}
ａ．逆リンクリスト 1
ListNode* reverseList(ListNode* head) {
ListNode* nextNode;
ListNode* prevNode = NULL;
while(head) {
nextNode = head -> next;
head -> next = prevNode;
prevNode = head;
head = nextNode;
}
return prevNode;
}
これは自分で試してみるべきです。これは上記の問題の拡張です。
c. リンクリスト内のノードの交換
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;
}
理解を深めるために、まず自分で試してみてください。
ａ．バイナリ ツリーをリンク リストに平坦化する
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;
}
リンク リストの問題に自信が持てるようになったら、これらの問題を解いてください。これらの質問は、さまざまな概念についての深い理解を問うものです。
ａ．k 個のソートされたリストを結合する
b. k-グループ内のノードを反転する
c. LFUキャッシュ
結論として
リンク リストに慣れるのに役立つ、LeetCode の最高の問題をいくつか提供しました。たとえ自分で質問を解決した場合でも、必ず LeetCode のディスカッション セクションにアクセスしてください。さまざまなコードや質問を解決するためのアプローチについて知ることができ、プログラマーにとって非常に役立ちます。
これらを解決すると、コンテストやコーディング コンテストで遭遇する可能性のある新しい問題を解決する直感が確実に得られるでしょう。これらは面接で繰り返し聞かれる質問の一つでもあります。
このブログを通じて、いくつかの重要な質問をリンク リストにまとめてみました。リンク リストを研究する際に、複数のプラットフォームでリンク リストについて広範囲に調査しましたが、これらの質問が最も役立つことがわかりました。これらの質問について知っていれば、間違いなく他の人よりも優位に立つことができます。
提案や建設的な批判は大歓迎です。また、このブログを通じて、データ構造とアルゴリズムの概念を見直し、コミュニティに貢献しようと努めています。これは、そもそもデータ構造とアルゴリズムを学ぶのに役立ちました。
![とにかく、リンクリストとは何ですか？[パート1]](https://post.nghiatu.com/assets/images/m/max/724/1*Xokk6XOjWyIGCBujkJsCzQ.jpeg)
