دستکاری لیست پیوندی، الگوی مصاحبه کدگذاری

Summarize this content to 400 words in Persian Lang

لیست پیوند شده

لیست پیوندی یک ساختار داده خطی متشکل از گره هایی است که در آن هر گره حاوی داده و یک مرجع (یا پیوند) به گره بعدی در دنباله است. برخلاف آرایه ها، لیست های پیوندی پویا هستند و به راحتی می توانند با افزودن یا حذف عناصر بدون نیاز به جابجایی عناصر دیگر، بزرگ یا کوچک شوند. این ویژگی لیست‌های پیوندی را برای پیاده‌سازی ساختارهای داده‌ای مانند پشته‌ها، صف‌ها و موارد دیگر که اندازه آن‌ها اغلب تغییر می‌کند مفید می‌سازد.

لیست پیوند معکوس

This question is part of Leetcode problems, question no. 206.

در اینجا کلاس Solution برای مشکل “Reverse Linked List” در C++ آمده است:

class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr; // Initialize previous pointer as nullptr
ListNode* current = head; // Initialize current pointer to head

while (current != nullptr) {
ListNode* nextNode = current->next; // Store next node
current->next = prev; // Reverse the current node’s pointer
prev = current; // Move prev pointer one step forward
current = nextNode; // Move current pointer one step forward
}

return prev; // Return the new head of the reversed list
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

لیست پیوند معکوس II

This question is part of Leetcode problems, question no. 92.

در اینجا کلاس Solution برای مشکل “Reverse Linked List II” در C++ آمده است:

class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
if (!head || left == right) return head;

ListNode* dummy = new ListNode(0); // Dummy node to simplify edge cases
dummy->next = head;
ListNode* prev = dummy;

// Move `prev` pointer to just before the `left` position
for (int i = 1; i left; ++i) {
prev = prev->next;
}

ListNode* current = prev->next; // `current` starts at `left`
ListNode* nextNode;

// Reverse the sublist between `left` and `right`
for (int i = 0; i right – left; ++i) {
nextNode = current->next;
current->next = nextNode->next;
nextNode->next = prev->next;
prev->next = nextNode;
}

return dummy->next; // Return the updated list starting from the original head
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

گره نهم را از انتهای لیست حذف کنید

This question is part of Leetcode problems, question no. 19.

در اینجا کلاس Solution برای مشکل “حذف گره نهم از انتهای لیست” در C++ آمده است:

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* first = dummy;
ListNode* second = dummy;

for (int i = 1; i n + 1; ++i) {
first = first->next;
}

while (first != nullptr) {
first = first->next;
second = second->next;
}

second->next = second->next->next;
return dummy->next;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

چرخه لیست پیوندی

This question is part of Leetcode problems, question no. 141.

در اینجا کلاس راه حل برای مسئله “چرخه لیست پیوندی” در C++ آمده است:

class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) return false;

ListNode* slow = head;
ListNode* fast = head->next;

while (slow != fast) {
if (!fast || !fast->next) return false;
slow = slow->next;
fast = fast->next->next;
}

return true;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

چرخه فهرست پیوندی II

This question is part of Leetcode problems, question no. 142.

در اینجا کلاس Solution برای مشکل “List Linked Cycle II” در C++ آمده است:

class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (!head || !head->next) return nullptr;

ListNode* slow = head;
ListNode* fast = head;

// Phase 1: Detect if there is a cycle
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
break;
}
}

// No cycle detected
if (fast == nullptr || fast->next == nullptr) {
return nullptr;
}

// Phase 2: Find the start node of the cycle
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}

return slow; // Both pointers meet at the start of the cycle
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

تقاطع دو لیست مرتبط

This question is part of Leetcode problems, question no. 160.

در اینجا کلاس Solution برای مشکل “تقاطع دو لیست پیوندی” در C++ آمده است:

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (!headA || !headB) return nullptr;

ListNode* ptrA = headA;
ListNode* ptrB = headB;

// Traverse both lists. When a pointer reaches the end, redirect it to the head of the other list.
// If they intersect, they will meet at the intersection node. If not, they will end up at the end of the lists together.
while (ptrA != ptrB) {
ptrA = ptrA ? ptrA->next : headB;
ptrB = ptrB ? ptrB->next : headA;
}

return ptrA; // Either the intersection node or nullptr if no intersection
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

دو عدد اضافه کنید

This question is part of Leetcode problems, question no. 2.

در اینجا کلاس Solution برای مشکل “افزودن دو عدد” در C++ آمده است:

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;
int carry = 0;

while (l1 || l2 || carry) {
int sum = carry;

if (l1) {
sum += l1->val;
l1 = l1->next;
}

if (l2) {
sum += l2->val;
l2 = l2->next;
}

carry = sum / 10;
current->next = new ListNode(sum % 10);
current = current->next;
}

return dummy->next;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

اضافه کردن دو عدد II

This question is part of Leetcode problems, question no. 445.

در اینجا کلاس Solution برای مسئله “Add Two Numbers II” در C++ آمده است:

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stackint> s1, s2;

// Push all values of l1 to stack s1
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}

// Push all values of l2 to stack s2
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}

ListNode* prev = nullptr;
int carry = 0;

// Process the stacks and build the result list
while (!s1.empty() || !s2.empty() || carry) {
int sum = carry;

if (!s1.empty()) {
sum += s1.top();
s1.pop();
}

if (!s2.empty()) {
sum += s2.top();
s2.pop();
}

carry = sum / 10;
ListNode* node = new ListNode(sum % 10);
node->next = prev;
prev = node;
}

return prev;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

گره ها را به صورت جفت عوض کنید

This question is part of Leetcode problems, question no. 24.

در اینجا کلاس Solution برای مشکل “تبادل گره ها به صورت جفت” در C++ آمده است:

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;

while (prev->next && prev->next->next) {
ListNode* first = prev->next;
ListNode* second = prev->next->next;

// Swap the nodes
first->next = second->next;
second->next = first;
prev->next = second;

// Move prev pointer two nodes ahead
prev = first;
}

return dummy->next;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

عناصر لیست پیوندی را حذف کنید

This question is part of Leetcode problems, question no. 203.

در اینجا کلاس Solution برای مشکل “Remove Linked List Elements” در C++ آمده است:

class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
// Remove leading nodes with the value ‘val’
while (head != nullptr && head->val == val) {
head = head->next;
}

// If the list becomes empty, return nullptr
if (head == nullptr) return head;

// Initialize current pointer
ListNode* current = head;

// Traverse the list and remove nodes with the value ‘val’
while (current->next != nullptr) {
if (current->next->val == val) {
current->next = current->next->next;
} else {
current = current->next;
}
}

return head;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

ادغام دو لیست مرتب شده

This question is part of Leetcode problems, question no. 21.

در اینجا کلاس Solution برای مشکل “Merge Two Sorted List” در C++ آمده است:

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// Create a dummy node to simplify the merging process
ListNode* dummy = new ListNode(0);
ListNode* current = dummy;

// Merge the two lists while both have remaining nodes
while (l1 != nullptr && l2 != nullptr) {
if (l1->val l2->val) {
current->next = l1;
l1 = l1->next;
} else {
current->next = l2;
l2 = l2->next;
}
current = current->next;
}

// Append any remaining nodes from either list
if (l1 != nullptr) {
current->next = l1;
} else {
current->next = l2;
}

// Return the merged list starting from dummy->next
return dummy->next;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

لیست پیوند خورده زوج زوج

This question is part of Leetcode problems, question no. 328.

در اینجا کلاس Solution برای مشکل “Odd Even Linked List” در C++ آمده است:

class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (head == nullptr) return nullptr;

// Initialize pointers for odd and even nodes
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even; // Keep track of the start of even list

// Iterate through the list to rearrange the nodes
while (even != nullptr && even->next != nullptr) {
odd->next = even->next; // Link the odd nodes
odd = odd->next; // Move to the next odd node
even->next = odd->next; // Link the even nodes
even = even->next; // Move to the next even node
}

// Attach the even list at the end of the odd list
odd->next = evenHead;

return head;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

فهرست پیوندی پالیندروم

This question is part of Leetcode problems, question no. 234.

در اینجا کلاس Solution برای مشکل “Palindrome Linked List” در C++ آمده است:

class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;

// Step 1: Find the middle of the linked list using the fast and slow pointer technique
ListNode* slow = head;
ListNode* fast = head;

while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

// Step 2: Reverse the second half of the list
ListNode* prev = nullptr;
while (slow) {
ListNode* nextNode = slow->next;
slow->next = prev;
prev = slow;
slow = nextNode;
}

// Step 3: Compare the first half and the reversed second half
ListNode* firstHalf = head;
ListNode* secondHalf = prev;

while (secondHalf) {
if (firstHalf->val != secondHalf->val) {
return false;
}
firstHalf = firstHalf->next;
secondHalf = secondHalf->next;
}

return true;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

وسط لیست پیوند شده

This question is part of Leetcode problems, question no. 876.

در اینجا کلاس Solution برای مشکل “Middle of the Linked List” در C++ آمده است:

class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;

// Move slow by one step and fast by two steps
// When fast reaches the end, slow will be at the middle
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}

return slow;
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;  // Initialize previous pointer as nullptr
        ListNode* current = head;  // Initialize current pointer to head

        while (current != nullptr) {
            ListNode* nextNode = current->next;  // Store next node
            current->next = prev;  // Reverse the current node's pointer
            prev = current;  // Move prev pointer one step forward
            current = nextNode;  // Move current pointer one step forward
        }

        return prev;  // Return the new head of the reversed list
    }
};

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        if (!head || left == right) return head;

        ListNode* dummy = new ListNode(0);  // Dummy node to simplify edge cases
        dummy->next = head;
        ListNode* prev = dummy;

        // Move `prev` pointer to just before the `left` position
        for (int i = 1; i  left; ++i) {
            prev = prev->next;
        }

        ListNode* current = prev->next;  // `current` starts at `left`
        ListNode* nextNode;

        // Reverse the sublist between `left` and `right`
        for (int i = 0; i  right - left; ++i) {
            nextNode = current->next;
            current->next = nextNode->next;
            nextNode->next = prev->next;
            prev->next = nextNode;
        }

        return dummy->next;  // Return the updated list starting from the original head
    }
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;

        for (int i = 1; i  n + 1; ++i) {
            first = first->next;
        }

        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }

        second->next = second->next->next;
        return dummy->next;
    }
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head || !head->next) return false;

        ListNode* slow = head;
        ListNode* fast = head->next;

        while (slow != fast) {
            if (!fast || !fast->next) return false;
            slow = slow->next;
            fast = fast->next->next;
        }

        return true;
    }
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr;

        ListNode* slow = head;
        ListNode* fast = head;

        // Phase 1: Detect if there is a cycle
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }

        // No cycle detected
        if (fast == nullptr || fast->next == nullptr) {
            return nullptr;
        }

        // Phase 2: Find the start node of the cycle
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return slow; // Both pointers meet at the start of the cycle
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) return nullptr;

        ListNode* ptrA = headA;
        ListNode* ptrB = headB;

        // Traverse both lists. When a pointer reaches the end, redirect it to the head of the other list.
        // If they intersect, they will meet at the intersection node. If not, they will end up at the end of the lists together.
        while (ptrA != ptrB) {
            ptrA = ptrA ? ptrA->next : headB;
            ptrB = ptrB ? ptrB->next : headA;
        }

        return ptrA; // Either the intersection node or nullptr if no intersection
    }
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        int carry = 0;

        while (l1 || l2 || carry) {
            int sum = carry;

            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }

            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }

            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
        }

        return dummy->next;
    }
};

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stackint> s1, s2;

        // Push all values of l1 to stack s1
        while (l1) {
            s1.push(l1->val);
            l1 = l1->next;
        }

        // Push all values of l2 to stack s2
        while (l2) {
            s2.push(l2->val);
            l2 = l2->next;
        }

        ListNode* prev = nullptr;
        int carry = 0;

        // Process the stacks and build the result list
        while (!s1.empty() || !s2.empty() || carry) {
            int sum = carry;

            if (!s1.empty()) {
                sum += s1.top();
                s1.pop();
            }

            if (!s2.empty()) {
                sum += s2.top();
                s2.pop();
            }

            carry = sum / 10;
            ListNode* node = new ListNode(sum % 10);
            node->next = prev;
            prev = node;
        }

        return prev;
    }
};

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;

        while (prev->next && prev->next->next) {
            ListNode* first = prev->next;
            ListNode* second = prev->next->next;

            // Swap the nodes
            first->next = second->next;
            second->next = first;
            prev->next = second;

            // Move prev pointer two nodes ahead
            prev = first;
        }

        return dummy->next;
    }
};

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // Remove leading nodes with the value 'val'
        while (head != nullptr && head->val == val) {
            head = head->next;
        }

        // If the list becomes empty, return nullptr
        if (head == nullptr) return head;

        // Initialize current pointer
        ListNode* current = head;

        // Traverse the list and remove nodes with the value 'val'
        while (current->next != nullptr) {
            if (current->next->val == val) {
                current->next = current->next->next;
            } else {
                current = current->next;
            }
        }

        return head;
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // Create a dummy node to simplify the merging process
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;

        // Merge the two lists while both have remaining nodes
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val  l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }

        // Append any remaining nodes from either list
        if (l1 != nullptr) {
            current->next = l1;
        } else {
            current->next = l2;
        }

        // Return the merged list starting from dummy->next
        return dummy->next;
    }
};

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == nullptr) return nullptr;

        // Initialize pointers for odd and even nodes
        ListNode* odd = head;
        ListNode* even = head->next;
        ListNode* evenHead = even; // Keep track of the start of even list

        // Iterate through the list to rearrange the nodes
        while (even != nullptr && even->next != nullptr) {
            odd->next = even->next; // Link the odd nodes
            odd = odd->next;        // Move to the next odd node
            even->next = odd->next; // Link the even nodes
            even = even->next;      // Move to the next even node
        }

        // Attach the even list at the end of the odd list
        odd->next = evenHead;

        return head;
    }
};

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;

        // Step 1: Find the middle of the linked list using the fast and slow pointer technique
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: Reverse the second half of the list
        ListNode* prev = nullptr;
        while (slow) {
            ListNode* nextNode = slow->next;
            slow->next = prev;
            prev = slow;
            slow = nextNode;
        }

        // Step 3: Compare the first half and the reversed second half
        ListNode* firstHalf = head;
        ListNode* secondHalf = prev;

        while (secondHalf) {
            if (firstHalf->val != secondHalf->val) {
                return false;
            }
            firstHalf = firstHalf->next;
            secondHalf = secondHalf->next;
        }

        return true;
    }
};

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        // Move slow by one step and fast by two steps
        // When fast reaches the end, slow will be at the middle
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};