Reverse linked list
I. Reverse Linked List
Một câu hỏi "dạo đầu" khá phổ biển được hỏi ở các công ty lớn như Google, Facebook, Uber, ... là reverse (đảo ngược) một singly linked list. Có thể nói rằng đây là một câu hỏi kinh điển về chủ đề 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 của nó. 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.
II. Đề bài
Viết một function nhận đầu vào là head của một Singly Linked List, reverse nó và trả về head của reverse linked list.
Đây là implement của Linked List mình sẽ sử dụng trong bài viết:
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
Sample Input:
head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 # the head node with value 0
Sample output:
head = 5 -> 4 -> 3 -> 2 -> 1 -> 0
Bài này có khá nhiều hướng giải quyết nhưng trong bài này mình sẽ chỉ đưa hai cách mà mình cho là tiêu biểu nhất.
1. Cách giải quyết 1: sử dụng list làm trung gian
Vì singly linked list chỉ có khả năng traverse theo một hướng (forward) trong khi list thì lại có khả năng reverse chính nó và traverse theo cả 2 hướng (forward, reversed) một cách dễ dàng. Nên hướng giải quyết của nhiều người khi gặp bài toán này là convert linked list về list, reversed list đó rồi dựng lại linked list bằng list đã được reversed. Dưới đây là mô tả cách giải của mình:
Minh hoạ cho cách giải quyết sử dụng list
Còn đây là lời giải của mình:
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
def reverseLinkedList(head):
lst = []
node = head
while node:
lst.append(node.value)
node = node.next
reversed_lst = reversed(lst)
head = LinkedList(next(reversed_lst))
current_node = head
for value in reversed_lst:
node = LinkedList(value)
current_node.next = node
current_node = node
return head 1.1 Phân tích space và time complexity
Chú tích: n là số lượng node của linked list đầu vào
Space complexity là O(n):
- Space complexity của việc construct một list n phần tử từ linked list là O(n)
- Space complexity của việc construct linked list từ list n phần tử là O(n)
- Do đó, space complexity của lời giải này là O(n)
Time complexity là O(n):
- Time complexity của việc construct một list n phần tử từ linked list là O(n)
- Time complexity của việc construct linked list từ list n phần tử là O(n)
- Do đó, time complexity của lời giải này là O(n)
2. Cách giải quyết 2: swap nodes in-place
Cách giải quyết sẽ được mô tả qua hình vẽ nghệch ngoạc sau:
Minh hoạ cho cách giải quyết swap các nodes
Diễn giải cách giải như sau:
- Chúng ta lưu vị trí của 3 nodes trong linked list (previous, current và following)
- Gắn next node của current thành previous
- Sau đó chúng ta tịnh tiến vị trí của 3 nodes (current → previous, following → current, current.next -> following) rồi gắn next node của current thành previous
- Cứ lặp lại các bước trên cho đến khi đạt được đến cuối linked list là chúng ta đã hoàn thành reverse một linked list
Còn đây là lời giải của mình:
class LinkedList: def __init__(self, value):
self.value = value
self.next = None
def reverseLinkedList(head):
previous_node, current_node = None, head
while current_node:
following_node = current_node.next
current_node.next = previous_node
previous_node, current_node = current_node, following_node
return previous_node
2.2 Phân tích space và time complexity
Chú tích: n là số lượng node của linked list đầu vào
Space comlexity là O(1)
- Cách giải này chúng ta chỉ swap các nodes ở linked list đầu vào - không phát sinh thêm space.
- Do đó, tổng space complexity là O(1)
Time complexity là O(n):
- Time complexity để lặp qua các nodes trong linked list là O(n)
- Do đó, tổng time complexity là O(n)
III. Kết luận
Hai cách giải trên chưa phải là tất cả các cách để reverse một 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!
