Đảo ngược một danh sách liên kết đơn lẻ. Example: Theo sát: Một danh sách được liên kết có thể được đảo ngược hoặc lặp đi lặp lại hoặc đệ quy. Bạn có thể thực hiện cả hai? Sử dụng một con trỏ trỏ đến một nút Nó rõ ràng rằng tại mỗi lần lặp, chúng ta di chuyển một nút để đứng trước đầu, vì vậy độ phức tạp của thời gian là o [n] nếu Dễ
Vấn đề
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULLGiải pháp - Lặp lại
x là đầu lúc đầu. Trong mỗi lần lặp nếu nó có nút tiếp theo y, hãy di chuyển nút tiếp theo để đứng trước đầu hiện tại và cập nhật con trỏ đầu lên y. Khi x không có nút tiếp theo, tức là đuôi của nó, kết thúc lần lặp.Sự phức tạp
n biểu thị cho các nút trong danh sách được liên kết này.the time complexity is O[n] if n denotes to counts of nodes in this linked list.
Nó tầm thường rằng nó chỉ sử dụng không gian O [1] thêm.O[1] extra space.
Giải pháp - đệ quy
Tại mỗi cuộc gọi chức năng, chúng tôi sẽ lấy đầu ra và thực hiện một cuộc gọi chức năng khác cho danh sách REST có đầu là nút tiếp theo của đầu hiện tại. Và nhớ đảo ngược liên kết giữa họ. Nó đã lưu ý rằng đầu mới sẽ được trả lại thông qua tất cả các cuộc gọi chức năng.
Sự phức tạp
Nó rõ ràng rằng tại mỗi lần lặp, chúng ta di chuyển một nút để đứng trước đầu, vì vậy độ phức tạp của thời gian là o [n] nếu n biểu thị cho các nút trong danh sách được liên kết này.time complexity will be O[n].
Nó tầm thường rằng nó chỉ sử dụng không gian O [1] thêm.space complexity is O[n] as well.
Những hiểu biết chính - Sử dụng hai con trỏ để đảo ngược danh sách. Khởi tạo con trỏ nút trước đó là không có.
Vấn đề LeetCode 206 yêu cầu chúng tôi đảo ngược danh sách được liên kết. Suy nghĩ đầu tiên của tôi là đi qua danh sách, theo dõi từng nút trong
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
Nỗ lực 1 - Sử dụng danh sách Python
Tôi đã quên một chút - đó là thêm nút cuối cùng của danh sách trên dòng 28. Sau khi tôi sửa nó, giải pháp đã vượt qua tất cả các thử nghiệm và đánh bại 19% giải pháp cho thời gian chạy và 23% cho bộ nhớ.
Cố gắng 2 - Tạo bản sao của Danh sách đảo ngược
Tôi nghĩ rằng tôi có thể bỏ qua việc xây dựng danh sách trung gian nếu tôi chỉ cập nhật con trỏ khi tôi đi qua danh sách.
Đây là cơ thể của nỗ lực thứ hai của tôi. Nó thất bại trong bài kiểm tra với một yếu tố danh sách.
Vấn đề là tôi cần phải trả lại
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
Cố gắng 3-Danh sách đảo ngược tại chỗ
Cách rõ ràng duy nhất có thể làm cho nó nhanh hơn là sửa đổi danh sách thay vì tạo một bản sao. Tôi sẽ thử điều đó mặc dù tôi không muốn sửa đổi các đối tượng được chuyển thành một chức năng. Tôi đoán nó chỉ là một con trỏ đến một danh sách chứ không phải danh sách.
Vì vậy, giải pháp này cập nhật các nút danh sách tại chỗ thay vì tạo một bản sao. Nó hoạt động bằng cách có ba gợi ý:
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
Để loại bỏ tất cả các bản sao dữ liệu, nó đã không tăng tốc độ giải pháp nhiều. Nó chỉ đánh bại 22% khi chạy. Tuy nhiên, nó đánh bại 46% trên bộ nhớ, vì vậy giải pháp nằm trong sân bóng để sử dụng bộ nhớ tối ưu.
Tại thời điểm này, tôi sẽ xem giải pháp Neetcode, và xem liệu tôi có thể nhận được bất kỳ mẹo nào để tăng tốc giải pháp nhiều hơn không.
Vì vậy, điều đó đã cho tôi một số ý tưởng về cách làm sạch mã của tôi. Cái nhìn sâu sắc chính là đặt
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp
x0. Với những hiểu biết này, mã đơn giản hóa xuống:Mặc dù đây là giải pháp tối ưu, nhưng nó chỉ đánh bại 16% các giải pháp trong thời gian chạy. Chắc chắn có một cái gì đó hài hước xảy ra với báo cáo hiệu suất thời gian chạy. Tuy nhiên, nó đã đánh bại 93% số bài nộp trên bộ nhớ, đó là một kết quả tốt đẹp.
Gói [lại
Tôi đã học được rất nhiều trong bài tập này và cải thiện các giải pháp của tôi khá nhiều trên đường đi. Có nhiều cách tiếp cận chắc chắn đã giúp tôi thấy những bất lợi của mỗi người và để đánh giá cao sự thanh lịch của giải pháp cuối cùng.
Đảo ngược một danh sách liên kết đơn lẻ. URL: //leetcode.com/probols/reverse-linked-list/# Definition for singly-linked list.
# class ListNode[object]:
# def __init__[self, x]:
# self.val = x
# self.next = None
class Solution[object]:
def reverseList[self, head]:
"""
:type head: ListNode
:rtype: ListNode
"""
if head == None:
return None
elif head != None and head.next == None:
return head
else:
temp = None
next_node = None
while head != None:
next_node = head.next
head.next = temp
temp = head
head = next_node
return temp