When doing some algorithm problems about single linked list , It is often necessary to reverse the single linked list to make the operation more convenient , But generally speaking, reverse , Common loop traversal single linked list , Create again using head interpolation
A single linked list to achieve reverse , But this is not only a bit of a waste of storage space , And it's easy to get confused , So if the required space complexity is O(1) Words , Then we can't use head interpolation to realize inverse .
At this time, a specific algorithm can be used to realize the inverse of the single linked list , Its thought is probably like this ：
Scan single linked list from beginning to end , Through specific means, make the latter node point to the former node in turn , such , A cycle goes on , Then the single linked list realizes the reverse order operation .
Namely from
A---->A---->A----->A------>A----->A----->
Become
<-----A<-----A<-----A<-----A<-----A<-----A
It may seem a little difficult to understand , I wrote my own draft paper and code , I hope it can help you understand :
Because I've been taking the postgraduate entrance examination recently , Tight time , Maybe it's a little irregular , hey , Hope for understanding
C Language implementation ：
// Put a single linked list L Local storage in reverse order LinkList ReverseList(LinkList &L){ if(L->next == NULL)
// If the single linked list is empty, it will be returned directly return L; LNode *q = L, *p = L->next, *temp;
// definition q Pointer to previous element ,p Pointer to the next element ,temp Is a temporary pointer q->next = NULL; // Set the pointer field of the end of the chain list to NULL while
(p != NULL){ q->data = p->data; // Assign the value of the latter element to the previous element temp = p->next;
//temp Temporarily record the next element p->next = q; //p The pointer now points in the opposite direction q, Namely q Will act as p Subsequent pointer to q = p; //q Move the pointer back p = temp;
//p Move the pointer back } q->data = 0; // Clear the data field of the final header node 0 L = q; // final take q Assign to L As head node return L; }
Running screenshot ：
Technology