Reverse linked list

788
23-09-2021
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:

reverse linked list

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:

reverse linked list swap nodes in-place

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!

SHARE