数据结构之链表反转

相对于数组来说，链表的操作让我总是特别不习惯，经常因为一个简单的操作自己要想半天。所以我决定把LeetCode题目里面一些经典的树的操作，链表的操作单独拎出来做。本身LeetCode里面很多也就是考的数据结构和算法的基础题。

因为对于单链表来说，本身只有一个比指向后面元素的指针，比如叫cur。所以想要反转链表，首先必定要有一个指针，指向当前指针的前一个元素，比如叫pre。只要将pre赋值给cur->next即可，但是，同时做完一次操作后，pre和cur都要后移一个位置。但是cur->next会被赋值掉，所以必定要加上一个辅助指针ne，在cur->next被赋值之前指向cur->next。在pre=cur->next前，要做ne=cur->next。在pre=cur->next之后，要做pre=cur，cur=ne操作。在整个操作外面套上一层循环，当前指针需不为空，while(cur!=NULL)。

在循环完之后，此时第一个元素变为链表最后的元素，head->next=NULL。

同时将头指针指向cur,head=pre。

struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
};
 

void reverse(ListNode *head){
	if(head==NULL||head->next==NULL)return; //如果head为NULL或者只有一个元素 
	ListNode* cur=head->next;  //记录当前指针指向位置 
	ListNode* pre=head;//记录当前指针的前一个位置 
	ListNode* ne;
	while(cur!=NULL){
		ne=cur->next;//辅助指针，指向当前指针的后一个位置 
		cur->next=pre;//当前指针指向前一个位置 
		pre=cur;//pre指针后移一个位置 
		cur=ne;//当前位置往后移一个位置 
	}
	head->next=NULL;//head指针指向最后的元素，head->next=NULL 
	head=pre;//head指针指向最后的元素 
}

数据结构之链表反转,布布扣,bubuko.com

数据结构之链表反转

原文：http://blog.csdn.net/whu_sky/article/details/22727367