Ngày 24 tháng Sam86 Club Choi Game Bài 7 năm 2020 - Máy tính

1. Mô tả bài toán

Đảo ngược một danh sách liên kết đơn.

Ví dụ:

Đầu vào: 1->2->3->4->5->NULL
Đầu ra: 5->4->3->2->1->NULL

Ghi chú: Việc đảo ngược danh sách có thể được thực hiện bằng cách sử dụng vòng lặp hoặc phương pháp đệ quy. Bạn có thể đồng thời triển khai cả hai thuật toán này không?

Nguồn bài toán: LeetCode

2. Cách tiếp cận giải quyết

Giải pháp sử dụng phương pháp đệ quy:

Phương pháp đệ quy thường dễ triển khai hơn. Các bước cụ thể như sau:

• Bước 1: Sử dụng con trỏ p để chỉ đến nút đầu tiên của danh sách, sau đó đảo ngược phần còn lại của danh sách từ nút thứ hai trở đi. Kết quả sẽ được lưu trữ trong biến q, đây là con trỏ đến đầu danh sách đã được đảo ngược.
• Bước 2: Đặt giá trị Next của p thành nil. Sau đó tìm kiếm nút cuối cùng của danh sách đã được đảo ngược (q) và đặt Next của nó trỏ về p.
• Bước 3: Tiếp tục quá trình đệ quy cho đến khi danh sách con chỉ còn một nút duy nhất thì dừng lại và trả về kết quả.

Giải pháp sử dụng vòng lặp:

Các bước chi tiết như sau:

• Bước 1: Khởi tạo ba con trỏ p, q, và r. Trong đó, p trỏ đến nút trước đó, q trỏ đến nút hiện tại, và r trỏ đến nút tiếp theo.
• Bước 2: Tiến hành đảo ngược bằng cách thay đổi giá trị của Next của q để nó trỏ về p.
• Bước 3: Di chuyển các con trỏ một bước tiến lên phía trước trên danh sách: p bây giờ sẽ là q, và q sẽ là r.
• Bước 4: Lặp lại các bước trên cho đến khi q trỏ đến nil, lúc này toàn bộ danh sách đã được đảo ngược hoàn chỉnh.

3. Mã nguồn Golang

Sử dụng phương pháp đệ quy:

func reverseList(head *ListNode) *ListNode {
	if nil == head || nil == head.Next {
		return head
	}
	p := head
	q := reverseList(head.Next)
	p.Next = nil
	r := q
	for nil != r.Next {
		r = r.Next
	}
	r.Next = p
	return q
}

Sử dụng phương pháp vòng lặp:

func reverseList(head *ListNode) *ListNode {
	if nil == head || nil == head.Next {
		return head
	}
	p := head
	q := p.Next
	p.Next = nil
	for nil != q {
		r := q.Next
		q.Next = p
		p = q
		q = r
	}
	return p
}

Từ tải game 789win khóa: #Golang #Thuật_toán