Bài toán shift linked list
I. Giới thiệu
Trong phần trước, mình đã giới thiệu cho các bạn về câu hỏi thuật toán kinh điển - Reverse linked list. Nay mình sẽ giới thiệu một câu hỏi kinh điển khác về linked list là shift 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 từng cách. 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 vào head của một Singly Linked List và một số k, shift list in place k vị trí và return head mới sau khi shifted. Số k có thể dương hoặc âm; đồng nghĩa với việc bạn phải xử lý 2 trường hợp đó là shift linked list về phía trước và về phía sau.
Input 1:
head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 k = 2 Output 1:
head = 4 -> 5 -> 0 -> 1 -> 2 -> 3 Input 2:
head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 k = -2 Output 2:
head = 2 -> 3 -> 4 -> 5 -> 0 -> 1 Ở các phần tiếp theo, mình sẽ đưa ra hai cách giải quyết bài toán này.
III. Cách giải quyết 1: Nối linked list thành một vòng lặp
Để có thể shift linked list tạo ra một linked list mới, chúng ta sẽ join linked list thành một loop linked list sau đó tìm head mới rồi phá vỡ vòng lặp ở new head để tạo ra linked list mới. Dưới đây là mô tả cách giải của mình:
Các bước chi tiết như sau:
Sử dụng phương án tiếp cận two pointers: Một pointer chỉ vào head, pointer còn lại di chuyển đến tail của linked list Sau đó gắn tail.next = head để tạo thành một vòng lặp nếu k > 0: head mới sẽ là node thứ (k % length) tính từ tail. Ví dụ nếu length của linked list là 6, k = 2 thì head mới sẽ là node thứ 2 tính từ tail; nếu k = 8 thì head mới cũng là node thứ 2 tính từ tail. nếu k < 0: head mới sẽ là node thứ ( |k| % length ) tính từ head. Ví dụ length của linked list là 6, k = -2 thì head mới sẽ là node thứ 2 tính từ head. Chúng ta break vòng lặp thành một linked list bình thường bằng cách gắn new_tail.next = None
Đây là 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 shiftLinkedList(head, k):
# Write your code here.
if k == 0:
return head
tail = head
length = 1
while tail.next:
tail = tail.next
length += 1
tail.next = head
if k > 0:
node = head
for _ in range((length - k - 1) % length):
node = node.next
new_head = node.next
node.next = None
return new_head
else:
node = tail
for _ in range(abs(k)):
node = node.next
new_head = node.next
node.next = None
return new_head Phân tích space và time complexity
Chú thích: n là số lượng node của linked list đầu vào
Space complexity là O(1):
Vì toàn bộ thuật toán xử lý ngay trên chính linked list đầu vào nên space complexity là constant - O(1)
Time complexity là O(n):
Time complexity để pointer tiến tới tail node là O(n)
Time complexity để join linked list là O(1)
Time complexity để tìm ra new head trong worst case là O(n)
Time complexity để break vòng lặp linked list là O(1)
Do đó, tổng time complexity là O(1)
Cách tiếp cận 2: sử dụng list làm trung gian
Tương tụ như linked list, chúng ta có thể giải quyết bài toán linked list 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:
Chúng ta convert từ linked list sang list Dựa trên tính chất khi shift đã đề cập ở cách tiếp cận 1, chúng ta tính magic number = k % length Sau đó, thực hiện shift trên list này với format là list[-magic:] + list[:-magic] Thực hiện dựng lại linked list trên list đã shift
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 shiftLinkedList(head, k):
# Write your code here.
lst = []
node = head
while node:
lst.append(node.value)
node = node.next
magic_n = k % len(lst)
shifted_lst = lst[-magic_n:] + lst[:-magic_n]
head = LinkedList(shifted_lst[0])
current_node = head
for value in shifted_lst[1:]:
node = LinkedList(value)
current_node.next =node
current_node = node
return head Phân tích space và time complexity:
Space complexity là O(n):
Space complexity để convert từ linked list sang list là O(n) Space complexity để dựng linked list từ list mới là O(n) Do đó, tổng space complexity là O(n)
Time complexity là O(n):
Time complexity để convert từ linked list sang list là O(n)
Time complexity để dựng linked list từ list mới 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 để shift 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!
