30 ngày chống COVID cùng Leetcode | Ngày 08

Cho một single linked list với head node là head. Bạn phải trả về node nằm ở vị trí giữa list này. Xem các ví dụ sau:

Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Ở đây node chính giữa là 3, ta sẽ trả về vị trí của node đó. Nếu bạn có tư tưởng chuyển list về mảng rồi tìm số chính giữa trả về thì không AC được, bởi nó yêu cầu trả về node của nó chứ không phải giá trị của node đó.

Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Có hai node nằm ở giữa trong ví dụ này, ta trả về node thứ 2.

Cách đầu tiên ta có thể nghĩ đến để giải bài này là dùng một biến count để đếm số phần tử của node, rồi duyệt một lần nữa return node thứ count/2.

Nhưng với 1 bài tập dễ thế này, ta có thể làm nó bằng nhiều cách hay hơn nhiểu.
Giải pháp đầu tiên là cho một biến count=0, ban đầu node chính giữa mid=head. Duyệt trên head, khi count lẻ lại cập nhật lại mid.

Giải pháp thứ hai, áp dụng bài tập hôm trước, sử dụng Two Pointer trong quyển sách của Narashimha. Node fast chạy nhanh gấp đôi lân node slow. Khi fast đi hết list thì slow đang ở vị trí giữa.


Bài tập ngày hôm nay làm tôi khá là không thỏa mãn, mong chờ một bài tập hay hơn từ Leetcode vào ngày mai. Hẹn gặp lại, cảm ơn !