单链表反转

本是古典何须时尚 2022-08-09 01:55 322阅读 0赞

把每次翻转看成左右两个部分的翻转，比如第一次翻转时把左边的第一个节点看成左部分，把右边的第二个节点看成右部分，来进行翻转，第二次翻转时把左边的两个节点看成一个左部分，右边的第三个节点看成右部分，那么第二次翻转就是左边的由第一个和第二个节点组成的左部分和右边的由第三个节点组成的右部分进行翻转，第三次翻转以此类推。。

这样的话我们让current指针始终指向每次反转的两部分中的左部分的最后一个节点，注意，左部分的节点为一个或者很多个，令temp=current->next这个指针指向右部分的节点，注意，右部分节点始终只有一个。So....看下面代码：

![Image 1][]

#include<iostream>
    using namespace std;
    struct ListNode{
    	int data;
    	ListNode *next;
    };
    ListNode* Create_Linklist(int *arr,int len)
    {
    	ListNode* head = new ListNode();
    	head->next = NULL;
    	ListNode* L = head;
    	for (int i = 0; i < len; i++)
    	{
    		ListNode* newn = new ListNode();
    		newn->data = arr[i];
    		newn->next = NULL;
    	    L->next = newn;
    		L = L->next;
    	}
    	return head;
    }
    void Reverse_LinkList(ListNode* &head)
    {
    	if ( head && head->next )
    	{
    		ListNode* current = head->next;   //current始终指向每次被反转后的节点中的最后一个，因此current的next节点就是要被反转的节点，即tamp
    		ListNode*  temp;   //temp始终指向被反转的节点，因此 temp 等于 current->next
    		while (current->next)
    		{
    			temp = current->next;
    			current->next = temp->next;
    			temp->next = head->next;
    			head->next = temp;
    		}
    	}
    }
    void Print_LinkList(ListNode* &head)
    {
    	if (head)
    	{
    		ListNode* L = head;
    		L = L->next;
    		while (L)
    		{
    			cout << L->data;
    			L = L->next;
    		}
    	}
    }
    void main(int argc, char *argv[])
    {
    	int arr1[] = { 1, 3, 5, 7 };
    	ListNode* head = Create_Linklist(arr1, sizeof(arr1) / sizeof(int));
    	Reverse_LinkList(head);
    	Print_LinkList(head);  
    }

[Image 1]: