单链表逆序也叫反转

迷南。 2022-06-15 00:43 180阅读 0赞

I have browsed many codes about the list reversed, most of which are hard to understand and complicated;

to reverse a single list, two methods can be required:

1; create a another list from the old list reversed, that is to say the new nodes are coming from the tail of the old list.

2; reverse the pointer; we need only to reverse the pointer from next to prior;

so we found the last method are better than first , because it is terse and without allocating new memory;

for example, original order is following:

prior cur next

○->○->○

reverse

○<-○<-○

ok, principle is easy to understand, implement it

#include
      
       
    using namespace std;
    
    struct Node
    {
    	int data;
    	struct Node *next;
    };
    
    struct Node *createList(const int & aiNum)
    {
    	struct Node *head = NULL;
    	struct Node *newPtr = NULL;
    	struct Node *cur;
    	int i = 0;
    	for (; i < aiNum; i++ )
    	{
    		if (!head)
    		{
    			head = (struct Node*)malloc(sizeof(Node));
    			head->data = i;
    			head->next = NULL;
    
    			cur = head;
    		}
    		else
    		{
    			newPtr = (struct Node*)malloc(sizeof(Node));
    			newPtr->data = i;
    			newPtr->next = NULL;
    			cur->next = newPtr;
    	    	cur = cur->next;
    		}
    	}
    	cur->next = NULL;
    
    	return head;
    }
    
    void printNode(struct Node * head)
    {
    	cout<<"print node"<<endl;
    	struct Node * lptr = head;
    	while (lptr)
    	{
    		cout<<lptr->data<<endl;
    		lptr = lptr->next;
    	}
    }
    
    void destroyList(struct Node * head)
    {
    	cout<<"destroy list"<<endl;
    	struct Node *cur = head;
    	int i = 0;
    	while (head)
    	{
    		cur = head;
    		cout<<cur->data<<endl;
    		head = head->next;
    		free(cur);
    	}
    }
    
    Node* reverseList(struct Node * head)
    {
    	Node *prior = head;
    	Node * cur = prior->next;
    	Node * next = NULL;
    
    	while (cur->next)//prior->cur->next
    	{
    		next = cur->next;
    		cur->next = prior;//prior<-cur->next
    		prior = cur;      //      prior cur  ;move to the next node for next loop
    		cur = next;
    	}
    	head->next = NULL;   //set the tail as NULL
    	cur->next = prior;  //the last loop , since the cur->next is null , 
    	                  //the pointer is still from head to cur,so we must reverse it additional
    	printNode(cur);
    
    	return cur;
    }
    void main()
    {
    	struct Node *head = createList(5);
    	printNode(head);
    	struct Node *rhead = reverseList(head);
    
    	destroyList(rhead);
    }

![0_1328883332NLkP.gif][]

[0_1328883332NLkP.gif]: /images/20220615/d02a4ded4b6c46f793df99e8c716a76a.png