naka-link na listahan: Ito ay isang naka-link na listahan na gusto naming baligtarin.
Pagkatapos ng reverse linked list: Ang nasa ibaba ang magiging resulta pagkatapos baligtarin ang naka-link na listahan sa itaas.
Sa halimbawang diagram sa itaas, makikita natin na ang head node at ang tail node ay nagbabago ng kanilang mga posisyon kapag binaligtad natin ang naka-link na listahan. Ang head node, na isa na ngayong tail node, ay tumuturo sa null node dahil isa na itong tail node.
Mga Hakbang sa Algorithm
- Lumilikha kami ng isang pangunahing pamamaraan at nagdedeklara ng ilang kinakailangang mga variable.
- Pagkatapos, ang aming susunod na hakbang ay upang lumikha ng isang paraan na maaaring lumikha ng isang naka-link na listahan. Tinutulungan kami ng paraang ito na gumawa ng naka-link na listahan.
- Ang susunod na hakbang ay gumawa ng paraan upang baligtarin ang naka-link na listahan. Sa pamamaraang ito, ipinapasa namin ang buong naka-link na listahan, at babaligtarin ng pamamaraang ito ang naka-link na listahan.
- Ngayon, kailangan namin ng isa pang paraan upang ipakita ang aming resulta pagkatapos itong baligtarin.
- Pagsasamahin namin ang lahat ng mga pamamaraan sa itaas sa aming pangunahing pamamaraan.
Ipapaliwanag namin ang reverse linked list gamit ang ilang pictorial form para mas madaling maunawaan. Kaya magsimula tayo sa halimbawa.
Ang nasa ibaba ay isang naka-link na listahan na gusto naming baligtarin.
Hakbang 1 . Ang berdeng kulay na node ay isang head node, na tumuturo sa unang node sa startup.
Hakbang 2. Sa susunod na hakbang, dadaanan namin ang buong naka-link na listahan hanggang sa hindi namin makuha ang null pointer sa tabi ng header node. Para diyan, magtatalaga kami sa susunod na node ng pansamantalang pangalan, tulad ng ipinapakita sa diagram sa ibaba.
Hakbang 3. Dahil mayroon kaming bagong reference node na pinangalanang 'pansamantala,' na makakatulong sa amin na lampasan ang buong naka-link na listahan hanggang sa hindi namin makuha ang null pointer, Para maitakda namin ang susunod na link ng header node bilang null, na hindi makakaapekto sa naka-link listahan tulad ng ipinapakita sa ibaba sa diagram. Ang null pointer sa tabi ng kasalukuyang node ay tinatawag na nakaraang node.
Hakbang 4. Ngayon, inilipat namin ang pansamantalang node sa susunod na node at ang kasalukuyang node sa nakaraang pansamantalang node. Kaya ngayon lumipat kami sa susunod na node. Binago rin namin ang nakaraang node mula sa null hanggang sa nakaraang node lamang ng kasalukuyang node. Kaya ngayon ang pansamantalang node ang bahala sa lahat ng mga traverse hanggang sa null pointer upang maitakda natin ang link ng kasalukuyang node sa nakaraang node, at ngayon ito ay tumuturo sa nakaraang node, tulad ng ipinapakita sa diagram sa ibaba.
Kaya't sinusunod namin ang parehong mga hakbang at, sa wakas, makakakuha kami ng isang reverse linked list.
Hakbang 5 .
Hakbang 6.
Hakbang 7.
Hakbang 8.
Hakbang 9.
Hakbang 10.
Hakbang 11.
Hakbang 12.
Hakbang 13.
Hakbang 14. Sa hakbang na ito, binaligtad ang aming naka-link na listahan.
C++ Program upang baligtarin ang isang naka-link na listahan
#includegamit namespace std ;
// Paraan upang lumikha ng node
struct node {
int halaga ;
node * susunod naNodePtr ;
} * nodeObject ;
walang bisa createLinkedList ( int n ) ;
walang bisa reverseLinkedList ( node ** nodeObject ) ;
walang bisa display ( ) ;
int pangunahing ( ) {
int n, halaga, bagay ;
cout << 'Ilang node ang gusto mong likhain =>: ' ;
kumakain >> n ;
createLinkedList ( n ) ;
cout << ' \n Impormasyon sa naka-link na listahan: \n ' ;
display ( ) ;
cout << ' \n Naka-link na listahan pagkatapos baligtarin \n ' ;
reverseLinkedList ( at nodeObject ) ;
display ( ) ;
bumalik 0 ;
}
// Ang paraang ito ay lilikha ng naka-link na listahan
walang bisa createLinkedList ( int n ) {
struct node * frontNode, * tempNode ;
int halaga, i ;
nodeObject = ( struct node * ) malloc ( sukat ng ( struct node ) ) ;
kung ( nodeObject == WALA )
cout << 'Hindi sapat para maalala ang alaala' ;
iba pa {
cout << 'Pakilagay ang impormasyon ng node 1 (numero lamang): ' ;
kumakain >> halaga ;
nodeObject - > halaga = halaga ;
nodeObject - > susunod naNodePtr = WALA ;
tempNode = nodeObject ;
para sa ( i = dalawa ; i <= n ; i ++ ) {
frontNode = ( struct node * ) malloc ( sukat ng ( struct node ) ) ;
// Kapag walang anumang node sa naka-link na listahan
kung ( frontNode == WALA ) {
cout << 'Hindi mailalaan ang memorya' ;
pahinga ;
}
iba pa {
cout << 'Pakilagay ang impormasyon ng node ' << i << ':' ;
kumakain >> halaga ;
frontNode - > halaga = halaga ;
frontNode - > susunod naNodePtr = WALA ;
tempNode - > susunod naNodePtr = frontNode ;
tempNode = tempNode - > susunod naNodePtr ;
}
}
}
}
walang bisa reverseLinkedList ( node ** nodeObject ) {
struct node * tempNode = WALA ;
struct node * nakaraangNode = WALA ;
struct node * kasalukuyangNode = ( * nodeObject ) ;
habang ( kasalukuyangNode ! = WALA ) {
tempNode = kasalukuyangNode - > susunod naNodePtr ;
kasalukuyangNode - > susunod naNodePtr = nakaraangNode ;
nakaraangNode = kasalukuyangNode ;
kasalukuyangNode = tempNode ;
}
( * nodeObject ) = nakaraangNode ;
}
walang bisa display ( ) {
struct node * tempNode ;
kung ( nodeObject == WALA ) {
cout << 'Walang laman ang linkedlist' ;
}
iba pa {
tempNode = nodeObject ;
habang ( tempNode ! = WALA )
{
cout << tempNode - > halaga << ' \t ' ;
tempNode = tempNode - > susunod naNodePtr ;
}
}
cout << endl ;
}
Output
Ilang node ang gusto mong gawin =>: 6Pakipasok ang impormasyon ng node 1 (numero lamang): 101
Mangyaring ipasok ang impormasyon ng node 2: 95
Mangyaring ipasok ang impormasyon ng node 3: 61
Mangyaring ipasok ang impormasyon ng node 4: 19
Mangyaring ipasok ang impormasyon ng node 5: 12
Mangyaring ipasok ang impormasyon ng node 6: 11
Impormasyon sa naka-link na listahan:
101 95 61 19 12 11
Naka-link na listahan pagkatapos baligtarin
11 12 19 61 95 101
Konklusyon
Sinuri ng artikulong ito ng LinuxHint kung paano i-reverse ang isang naka-link na listahan sa C++. Mayroong ilang iba pang mga paraan upang baligtarin ang isang naka-link na listahan, ngunit ito ay isang napaka-karaniwang paraan upang baligtarin ang isang naka-link na listahan. Nasa sa iyo na magpasya kung paano mo gustong lutasin ang iyong mga problema, ngunit sa pangkalahatan ang reverse linked list function ay dapat na isang simpleng loop na may pointer swaps.