TungDS
739
18-10-2021
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.
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.
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:
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
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)
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:
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)
TIme complexity là O(n+m)
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!