Untitled Document
Untitled Document
Video 1: Lecture 44: Linked List & its types - Singly, Doubly,
Circular etc.
Concept Breakdown
Node(int data) {
this->data = data;
this->next = NULL;
}
};
○
● Linked List Implementation (Singly Linked List)
○
● Traversal of a Singly Linked List
○
● Insertion at the Head of a Singly Linked List
○
● Types of Linked Lists (Brief Introduction)
Problems Solved
int main() {
// Creating nodes
Node* node1 = new Node(10);
Node* node2 = new Node(20);
// Linking nodes
node1->next = node2;
○
○ Additional Example:
■ Problem Statement: Create three nodes with data 5,
15, and 25, and link them sequentially.
■ High-Level Approach: Similar to the video, create
Node objects and set the next pointers.
Step-by-step Code:
Node* first = new Node(5);
Node* second = new Node(15);
Node* third = new Node(25);
first->next = second;
second->next = third;
third->next = NULL;
■
● Insertion at the Head
int main() {
Node* head = new Node(10);
insertAtHead(head, 12);
// ... (printing the list would show 12 -> 10 -> NULL)
}
○
○ Additional Example:
■ Problem Statement: Start with an empty linked list
(head is NULL). Insert the values 7, then 14, then
21 at the head.
■ High-Level Approach: Call insertAtHead repeatedly.
Step-by-step Code:
Node* head = NULL;
insertAtHead(head, 21); // List: 21 -> NULL
insertAtHead(head, 14); // List: 14 -> 21 -> NULL
insertAtHead(head, 7); // List: 7 -> 14 -> 21 -> NULL
// Verification (printing)
Node* temp = head;
while (temp != NULL) {
std::cout << temp->data << (temp->next ? " -> " : " -> NULL")
<< std::endl;
temp = temp->next;
}
// Output:
// 7 -> 14
// 14 -> 21
// 21 -> NULL
■
Concept Breakdown
○
● Finding the Middle Node of a Singly Linked List (Two-Pointer
Approach - Slow and Fast)
○
Problems Solved
● Reversing a Linked List (Iterative)
■ Annotated Steps:
1.
slow = 1, fast = 1.
2.
fast = 3, slow = 2.
3.
fast = 5, slow = 3.
4.
fast = NULL (fast->next is 6,
fast->next->next is NULL). Loop terminates.
■ Output: The middle node is 3.
■ Annotated Steps:
Concept Breakdown
Pseudo-code:
function reverseKGroup(head, k):
if head is NULL:
return NULL
○
● Detecting a Cycle (Loop) in a Linked List (Floyd's
Cycle-Finding Algorithm / Tortoise and Hare)
○
Problems Solved
■ Annotated Steps:
■ Annotated Steps:
Video 4: Lecture 47: Detect & Remove Loop in Linked List [Approach
Discussion + Optimised Implementation]
Concept Breakdown
○
● Removing a Loop from a Linked List
○
Problems Solved
Concept Breakdown
Problems Solved
● Sorted List Optimisation: For sorted lists, the O(n) time and
O(1) space solution is efficient as duplicates are adjacent.
● Unsorted List Trade-off: For unsorted lists, using a hash set
provides an O(n) time complexity solution (average case for
hash operations) but requires O(n) extra space to store the
seen elements.
● Alternative for Unsorted (No Extra Space): One could solve the
unsorted case with O(n^2) time and O(1) space by iterating
through the list with one pointer and then for each node,
iterating through the rest of the list to find and remove
duplicates.
● Memory Management: When removing nodes, it's crucial to
deallocate the memory using delete (in C++) to prevent memory
leaks.
Video 6: Lecture 49: Merge 2 Sorted Linked Lists || Sort 0s, 1s and
2s in Linked List
Concept Breakdown
if (head1 != NULL) {
tail->next = head1;
} else if (head2 != NULL) {
tail->next = head2;
}
○
● Sorting a Linked List of 0s, 1s, and 2s (Data Replacement vs.
Pointer Manipulation)
head = zeroHead->next;
○
Problems Solved
Concept Breakdown
○
Problems Solved
middle = findMiddle(head)
secondHalfHead = reverse(middle->next)
middle->next = NULL // Separate the two halves
head1 = head
head2 = secondHalfHead
isPal = true
while head2 is not NULL:
if head1->data != head2->data:
isPal = false
break
head1 = head1->next
head2 = head2->next
return isPal
○
○ Additional Example:
■ Problem Statement: Check if the list 1 -> 2 -> 3 ->
2 -> 1 -> NULL is a palindrome.
■ Annotated Steps:
1.Middle node is 3.
2.Second half (3 -> 2 -> 1) becomes (1 -> 2 ->
3) after reversal.
3.Compare (1 -> 2) with (1 -> 2). They match.
4.The list is a palindrome.
■ Output: True.
■ Annotated Steps:
1.Middle node is 2.
2.Second half (3 -> 1) becomes (1 -> 3) after
reversal.
3.Compare (1 -> 2) with (1 -> 3). They don't
match at the second node.
4.The list is not a palindrome.
■ Output: False.
Concept Breakdown
○
Problems Solved
carry = sum / 10
digit = sum % 10
newNode = new Node(digit)
tail->next = newNode
tail = newNode
resultHead = dummyHead->next
delete dummyHead
return resultHead
○
○ Additional Example:
■ Problem Statement: Add the numbers represented by
list1: 5 -> 6 -> 3 -> NULL (365) and list2: 8 -> 4
-> 2 -> NULL (248).
■ High-Level Approach: Apply the addTwoLists
algorithm.
■ Annotated Steps:
1. Iteration 1: sum = 0 + 5 + 8 = 13. carry = 1,
digit = 3. Result: 3 -> NULL.
2. Iteration 2: sum = 1 + 6 + 4 = 11. carry = 1,
digit = 1. Result: 3 -> 1 -> NULL.
3. Iteration 3: sum = 1 + 3 + 2 = 6. carry = 0,
digit = 6. Result: 3 -> 1 -> 6 -> NULL.
4. Both lists are NULL, but carry is 0. Loop
ends.
■ Output: 3 -> 1 -> 6 -> NULL (represents 613, which
is 365 + 248).
Video 9: Lecture 52: Clone a Linked List with Random Pointers || C++
Placement Course
Concept Breakdown
○ High-Level Approaches:
Problems Solved
return clonedHead
○
○ Additional Example:
■ Problem Statement: Clone a list: A(random=C) ->
B(random=A) -> C(random=NULL) -> NULL.
■ High-Level Approach: Use the hashing method.
■ Annotated Steps:
1. Create clone A', B', C'. oldToNewMap = {A:
A', B: B', C: C'}. Cloned list: A' -> B' ->
C' -> NULL.
2.Set next pointers: A'->next = B', B'->next =
C', C'->next = NULL (using map).
3.Set random pointers:
■ A'->random = oldToNewMap.get(A->random)
= oldToNewMap.get(C) = C'.
■ B'->random = oldToNewMap.get(B->random)
= oldToNewMap.get(A) = A'.
■ C'->random = oldToNewMap.get(C->random)
= oldToNewMap.get(NULL) = NULL.
■ Output: Cloned list: A'(random=C') -> B'(random=A')
-> C'(random=NULL) -> NULL.
Concept Breakdown
○
Problems Solved
mid = findMiddle(head)
left = head
right = mid->next
mid->next = NULL // Break list into two
sortedLeft = sortList(left)
sortedRight = sortList(right)
return mergedList
○
○ Additional Example:
■ Problem Statement: Sort the list 3 -> 1 -> 4 -> 1
-> 5 -> 9 -> 2 -> 6 -> NULL using merge sort.
■ High-Level Approach: Apply the merge sort
algorithm.
■ Annotated Steps (Conceptual):
1.Divide: and.
2.Recursively divide further until
single-element lists are obtained.
3.Conquer (Sort single elements - already
sorted).
4.Combine (Merge):
■ Merge and ->.
■ Merge and ->.
■ Merge and ->.
■ Merge and ->.
■ Merge and ->.
■ Merge and ->.
■ Merge and ->.
■ Output: 1 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 9 ->
NULL.
Concept Breakdown
childTail = childHead
while childTail->next is not NULL:
childTail = childTail->next
○
Problems Solved
■
■ High-Level Approach: Apply the flattening
algorithm.
■ Annotated Steps (Conceptual):
1. At node 2, child is 4. Connect 2->next to 4,
and 4->prev to 2. Sub-structure becomes: 1
<-> 2 <-> 4 <-> 5 -> NULL (child of 2
integrated).
2. At node 5, child is 6. Connect 5->next to 6,
and 6->prev to 5. Sub-structure becomes: 1
<-> 2 <-> 4 <-> 5 <-> 6 -> NULL.
3.Continue traversing the main level. Node 3 is
reached. No child.
■ Output: 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 3 -> NULL
(and the prev pointers are also correctly set).