[DSA_02] Leetcode: #19, #21

---

Just a note

19

Prob:

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Intuition:

1. Reverse linked list (1 vòng while), delete node Nth như bình thường (1 vòng while), Reverse lại (1 vòng while) => 3 Pass (vẫn O(L), không dùng thêm space)

2. Xóa node Nth từ end <=> xóa node L - N + 1 với L là length tư head. Vậy cho chay 1 vòng while tìm L, sau đó xóa node thứ L-N+1 từ head => 2 Pass (O(L) và O(1) space)

3. Kĩ thuật 2 con trỏ: cho 1 con trỏ chạy đên Nth từ head trước, bây giờ 2 con đang cách nhau Nth. Sau đó chạy 2 con trỏ từng bước đến khi con trỏ 1 đến end, bây giờ con trỏ 2 đang ơ (L - N )th. Sau đó nối => Có thê xem là 1 pass (O(L) và O(1) space)

!Trick:

Dùng môt con trỏ gọi là dummy. Node<List_ItemType> *dummy = new Node<List_ItemType>(); dummy->next = this->head;.
Để khi xóa phần tử đầu tiên khỏi linked list, ta không càn chia riêng trường hợp đó ra, mà dùng luôn pTemp->next (ở đây pTemp là dummy)

21

Prob:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4

Intuition:

Tạo 1 head mới cho linkedlist sắp merge. xét lần lượt từng cặp số của 2 linked list, số nào bé hơn thì nối vào. Đên khi 1 trong 2 list rỗng, nối tất cả linked list còn lại vào merge list.