danh sách liên kết: Đây là một danh sách liên kết mà chúng tôi muốn đảo ngược.
Sau khi đảo ngược danh sách liên kết: Dưới đây sẽ là kết quả sau khi đảo ngược danh sách liên kết ở trên.
Trong sơ đồ ví dụ trên, chúng ta có thể thấy rằng nút đầu và nút đuôi thay đổi vị trí của chúng khi chúng ta đảo ngược danh sách được liên kết. Nút đầu, bây giờ là nút đuôi, trỏ đến nút rỗng vì nó bây giờ là nút đuôi.
Các bước thuật toán
- Chúng tôi tạo một phương thức chính và khai báo một số biến cần thiết.
- Sau đó, bước tiếp theo của chúng ta là tạo một phương thức có thể tạo danh sách được liên kết. Phương thức này giúp chúng ta tạo danh sách liên kết.
- Bước tiếp theo là tạo phương thức đảo ngược danh sách liên kết. Trong phương thức này, chúng tôi chuyển toàn bộ danh sách được liên kết và phương thức này sẽ đảo ngược danh sách được liên kết.
- Bây giờ, chúng ta cần một phương thức khác để hiển thị kết quả sau khi đảo ngược nó.
- Chúng tôi sẽ kết hợp tất cả các phương pháp trên thành phương pháp chính của chúng tôi.
Chúng tôi sẽ giải thích danh sách liên kết ngược bằng cách sử dụng một số hình ảnh để dễ hiểu hơn. Vì vậy, hãy bắt đầu với ví dụ.
Dưới đây là một danh sách liên kết mà chúng tôi muốn đảo ngược.
Bước 1 . Nút màu xanh lá cây là nút đầu, trỏ đến nút đầu tiên trong quá trình khởi động.
Bước 2. Trong bước tiếp theo, chúng tôi sẽ duyệt qua toàn bộ danh sách được liên kết cho đến khi chúng tôi không nhận được con trỏ null bên cạnh nút tiêu đề. Đối với điều đó, chúng tôi sẽ gán cho nút tiếp theo một tên tạm thời, như thể hiện trong sơ đồ bên dưới.
Bước 3. Vì chúng tôi có một nút tham chiếu mới có tên là “tạm thời”, nút này có thể giúp chúng tôi duyệt qua toàn bộ danh sách được liên kết cho đến khi chúng tôi không nhận được con trỏ null, Vì vậy, chúng tôi có thể đặt liên kết tiếp theo của nút tiêu đề là null, điều này sẽ không ảnh hưởng đến liên kết được liên kết danh sách như thể hiện dưới đây trong sơ đồ. Con trỏ null bên cạnh nút hiện tại được gọi là nút trước đó.
Bước 4. Bây giờ, chúng tôi di chuyển nút tạm thời sang nút tiếp theo và nút hiện tại sang nút tạm thời trước đó. Vì vậy, bây giờ chúng tôi đã chuyển sang nút tiếp theo. Chúng tôi cũng thay đổi nút trước đó từ null thành nút trước đó của nút hiện tại. Vì vậy, bây giờ nút tạm thời sẽ xử lý tất cả các lần di chuyển cho đến con trỏ null để chúng ta có thể đặt liên kết của nút hiện tại với nút trước đó và bây giờ nó đang trỏ đến nút trước đó, như thể hiện trong sơ đồ bên dưới.
Vì vậy, chúng tôi làm theo các bước tương tự và cuối cùng, chúng tôi sẽ nhận được một danh sách liên kết đảo ngược.
Bước 5 .
Bước 6.
Bước 7.
Bước 8.
Bước 9.
Bước 10.
Bước 11.
Bước 12.
Bước 13.
Bước 14. Ở bước này, danh sách được liên kết của chúng tôi đã đảo ngược.
Chương trình C++ đảo ngược danh sách liên kết
#includesử dụng không gian tên tiêu chuẩn ;
// Phương thức tạo nút
cấu trúc nút {
int giá trị ;
nút * tiếp theoNodePtr ;
} * nútObject ;
khoảng trống tạoLinkedList ( int N ) ;
khoảng trống ReverseLinkedList ( nút ** nútObject ) ;
khoảng trống trưng bày ( ) ;
int chính ( ) {
int n,giá trị,mục ;
cout << 'Bạn muốn tạo bao nhiêu nút =>:' ;
Ăn >> N ;
tạoLinkedList ( N ) ;
cout << ' \N Thông tin trong danh sách liên kết: \N ' ;
trưng bày ( ) ;
cout << ' \N Danh sách liên kết sau khi đảo ngược \N ' ;
ReverseLinkedList ( & nútObject ) ;
trưng bày ( ) ;
trở về 0 ;
}
// Phương thức này sẽ tạo danh sách liên kết
khoảng trống tạoLinkedList ( int N ) {
cấu trúc nút * nút phía trước, * tempNode ;
int giá trị, tôi ;
nútObject = ( cấu trúc nút * ) malloc ( kích thước của ( cấu trúc nút ) ) ;
nếu ( nútObject == VÔ GIÁ TRỊ )
cout << 'Không đủ để khẳng định bộ nhớ' ;
khác {
cout << 'Vui lòng nhập thông tin của nút 1 (chỉ số):' ;
Ăn >> giá trị ;
nútObject - > giá trị = giá trị ;
nútObject - > tiếp theoNodePtr = VÔ GIÁ TRỊ ;
tempNode = nútObject ;
vì ( tôi = hai ; tôi <= N ; tôi ++ ) {
nút phía trước = ( cấu trúc nút * ) malloc ( kích thước của ( cấu trúc nút ) ) ;
// Khi không có nút nào trong danh sách liên kết
nếu ( nút phía trước == VÔ GIÁ TRỊ ) {
cout << 'Không thể cấp phát bộ nhớ' ;
phá vỡ ;
}
khác {
cout << 'Vui lòng nhập thông tin của nút' << tôi << ':' ;
Ăn >> giá trị ;
nút phía trước - > giá trị = giá trị ;
nút phía trước - > tiếp theoNodePtr = VÔ GIÁ TRỊ ;
tempNode - > tiếp theoNodePtr = nút phía trước ;
tempNode = tempNode - > tiếp theoNodePtr ;
}
}
}
}
khoảng trống ReverseLinkedList ( nút ** nútObject ) {
cấu trúc nút * tempNode = VÔ GIÁ TRỊ ;
cấu trúc nút * trướcNode = VÔ GIÁ TRỊ ;
cấu trúc nút * hiện tạiNode = ( * nútObject ) ;
trong khi ( hiện tạiNode ! = VÔ GIÁ TRỊ ) {
tempNode = hiện tạiNode - > tiếp theoNodePtr ;
hiện tạiNode - > tiếp theoNodePtr = trướcNode ;
trướcNode = hiện tạiNode ;
hiện tạiNode = tempNode ;
}
( * nútObject ) = trướcNode ;
}
khoảng trống trưng bày ( ) {
cấu trúc nút * tempNode ;
nếu ( nútObject == VÔ GIÁ TRỊ ) {
cout << 'Danh sách liên kết trống' ;
}
khác {
tempNode = nútObject ;
trong khi ( tempNode ! = VÔ GIÁ TRỊ )
{
cout << tempNode - > giá trị << ' \t ' ;
tempNode = tempNode - > tiếp theoNodePtr ;
}
}
cout << kết thúc ;
}
đầu ra
Bạn muốn tạo bao nhiêu nút =>: 6Vui lòng nhập thông tin của nút 1 (chỉ số): 101
Vui lòng nhập thông tin của nút 2: 95
Vui lòng nhập thông tin của nút 3: 61
Vui lòng nhập thông tin của nút 4: 19
Vui lòng nhập thông tin của nút 5: 12
Vui lòng nhập thông tin của nút 6: 11
Thông tin trong danh sách liên kết:
101 95 61 19 12 11
Danh sách liên kết sau khi đảo ngược
11 12 19 61 95 101
Sự kết luận
Bài viết LinuxHint này đã xem xét cách đảo ngược danh sách liên kết trong C++. Có một số phương pháp khác để đảo ngược danh sách được liên kết, nhưng đây là phương pháp rất phổ biến để đảo ngược danh sách được liên kết. Tùy bạn quyết định cách bạn muốn giải quyết vấn đề của mình, nhưng nhìn chung hàm danh sách liên kết ngược phải là một vòng lặp đơn giản với các hoán đổi con trỏ.