TungDS
739
18-10-2021
Bài toán Merge Linked List
Giới thiệu
Tiếp tục chủ đề Linked List trong series Algorithm & Data Structure, nay mình sẽ giới thiệu cho các bạn bài toán Merge Linked List. Trong bài viết này, mình sẽ đưa ra 2 hướng giải quyết bài toán và phân tích space và time complexity. Mình sẽ giả sử rằng bạn đã biết về cấu trúc dữ liệu linked list khi đọc bài này. Nếu không, bạn có thể đọc tài liệu "Basic linked list" của Đại học Stanford, Mỹ tại đây.
Đề bài
Viết một function nhận vào 2 head của hai sorted Singly linked list. Viết một function merge hai linked list và return head của sorted linked list đã merge.
Input:
head_1 = 2 -> 6 -> 7 -> 8 head_2 = 1 -> 3 -> 4 -> 5 -> 9 -> 10 Output:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 Ở phần tiếp theo, mình sẽ đưa ra hai cách giải quyết bài toán này.
Cách giải quyết 1: sử dụng list làm trung gian
Tương tự như các bài toán về linked list trước, chúng ta có thể giải quyết bài toán này thông qua list rồi dựng lại một linked list. Dưới đây là mô tả của mình:
Các bước chi tiết như sau:
- Đầu tiên chúng ta convert hai linked lists thành 2 list
- Sau đó chúng ta merge 2 list đó lại với nhau
- Sort list mới tạo thành
- Construct linked list mới dựa trên sorted list
Lời giải của mình cho cách tiếp cận này:
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
def mergeLinkedLists(headOne, headTwo):
lst1 = listify(headOne)
lst2 = listify(headTwo)
lst1.extend(lst2)
lst1.sort()
head = LinkedList(lst1[0])
node = head
for n in lst1[1:]:
node.next = LinkedList(n)
node = node.next
return head
def listify(head):
lst = []
node = head
while node:
lst.append(node.value)
node = node.next
return lst
Phân tích space và time complexity:
Ghi chú: m và n lần lượt là độ dài của hai linked list
Space complexity là O(n + m)
Space complexity để listify hai linked list là O(n + m) Space complexity để construct linked list từ list mới là O(n + m) Do đó, tổng space complexity là O(n + m)
TIme complexity là O((n+m)log(n+m))
Time complexity để listify hai linked list là O(n+m) Time complexity để sort list là O((n + m)log(n + m)) Time complexity để construct linked list từ list mới là O(n+m) Do đó, tổng time complexity là O((n + m)log(n + m)
Cách giải quyết 2: Merge in place
Thay vì thông qua list như cách trên, cách này chúng ta sẽ merge hai linked list ngay trên chính một cái đã chọn. Dưới đây là mô tả của mình:
Các bước chi tiết như sau:
- Chọn head có giá trị nhỏ hơn làm trung tâm - nơi sẽ insert các nodes của linked list còn lại
- Sử dụng hai pointers nếu để insert nodes vào linked list trung tâm theo thứ tự.
- Lặp đến hết nodes ở cả hai linked list
Lời giải của mình như sau:
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
def mergeLinkedLists(headOne, headTwo):
p1 = headOne
p1_prev = None
p2 = headTwo
while p1 and p2:
if p1.value < p2.value:
p1_prev = p1
p1 = p1.next
else:
if p1_prev:
p1_prev.next = p2
p1_prev = p2
p2 = p2.next
p1_prev.next = p1
if not p1:
p1_prev.next = p2
return headOne if headOne.value < headTwo.value else headTwo
Phân tích space và time complexity:
Ghi chú: m và n lần lượt là độ dài của hai linked list
Space complexity là O(1)
- Vì toàn bộ thuật toán được merge in place nên space complexity constant - O(1)
TIme complexity là O(n+m)
- Time complexity để lặp qua từng phần tử của hai linked list là O(n + m)
III. Kết luận
Hai cách giải trên chưa phải là tất cả các cách để merge hai linked list nhưng là 2 cách khá tiêu biểu cho bài toán kinh điển này. Mong rằng bài blog này có thể giúp bạn trên một phương diện nào đó. Nếu bạn thấy bài blog thú vị hãy chia sẻ để nhiều người biết đến hơn nhé Và hãy đón chờ thêm các bài blog của mình về chủ đề Data Structure & Algorithm trên tech blog của BizFly Cloud nha!
