Linked List
A Linked List is a linear data structure consisting of nodes where each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists are dynamic and can easily grow or shrink in size by adding or removing elements without needing to shift other elements. This property makes linked lists particularly useful for implementing data structures such as stacks, queues, and others where the size can frequently change.
Reverse Linked List
This question is part of Leetcode problems, question no. 206.
Here’s the Solution class for the "Reverse Linked List" problem in 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
}
};
Reverse Linked List II
This question is part of Leetcode problems, question no. 92.
Here’s the Solution class for the "Reverse Linked List II" problem in 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
}
};
Remove Nth Node From End of List
This question is part of Leetcode problems, question no. 19.
Here’s the Solution class for the "Remove Nth Node From End of List" problem in 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;
}
};
Linked List Cycle
This question is part of Leetcode problems, question no. 141.
Here’s the Solution class for the "Linked List Cycle" problem in 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;
}
};
Linked List Cycle II
This question is part of Leetcode problems, question no. 142.
Here’s the Solution class for the "Linked List Cycle II" problem in 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
}
};
Intersection of Two Linked Lists
This question is part of Leetcode problems, question no. 160.
Here’s the Solution class for the "Intersection of Two Linked Lists" problem in 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
}
};
Add Two Numbers
This question is part of Leetcode problems, question no. 2.
Here’s the Solution class for the "Add Two Numbers" problem in 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;
}
};
Add Two Numbers II
This question is part of Leetcode problems, question no. 445.
Here’s the Solution class for the "Add Two Numbers II" problem in C++:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> 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;
}
};
Swap Nodes in Pairs
This question is part of Leetcode problems, question no. 24.
Here’s the Solution class for the "Swap Nodes in Pairs" problem in 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;
}
};
Remove Linked List Elements
This question is part of Leetcode problems, question no. 203.
Here’s the Solution class for the "Remove Linked List Elements" problem in 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;
}
};
Merge Two Sorted Lists
This question is part of Leetcode problems, question no. 21.
Here’s the Solution class for the "Merge Two Sorted Lists" problem in 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;
}
};
Odd Even Linked List
This question is part of Leetcode problems, question no. 328.
Here’s the Solution class for the "Odd Even Linked List" problem in 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;
}
};
Palindrome Linked List
This question is part of Leetcode problems, question no. 234.
Here’s the Solution class for the "Palindrome Linked List" problem in 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;
}
};
Middle of the Linked List
This question is part of Leetcode problems, question no. 876.
Here’s the Solution class for the "Middle of the Linked List" problem in 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;
}
};
Top comments (0)