反转链表C++实现

实现链表的反转有两个方法：

（1）定义一个新的链表，实现链表反转，但是会造成内存空间的浪费；

（2）只需要改变next指针的方向，就可以直接对链表反转，如下面动画所示：

步骤如下：

1.使cur指针指向现在的头结点；

2.初始化一个pre指针，初始化为null；

3.将cur->next用tmp存一下，改变next的方向（使用循环），最后cur指向null，返回pre为新的头结点。

//Solution 1 --双指针法 
ListNode* reverseList(ListNode* head) {
	ListNode* cur = head;
	ListNode* pre = NULL;
	while(cur != NULL) {
		ListNode* tmp = cur->next;
		cur->next = pre;
		pre = cur;
		cur = tmp;
	}
	return pre;
}

可以使用递归法实现：

//Solution 2 --递归法
ListNode* reverseList(ListNode* head) {
	return reverse(NULL,head);
}
 
ListNode* reverse(ListNode* pre,ListNode* cur) {
	if (cur == NULL) {
		return pre;
	}
	ListNode* tmp = cur->next;
	cur->next = pre;
	return(cur,tmp)
}