逆置链表（c++）

逆置链表（c++） 逆置链表（自学算法第二篇） 题目描述：

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。 

 数据范围： n≤1000

要求：

空间复杂度 O(1) ，时间复杂度 O(n)。

示例：

如当输入链表{1,2,3}时，

经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

转换过程如下图所示：

输入：{1，2，3}
返回值：{3，2，1}

输入：{}
返回值：{}
说明：空链表则输出空

题目分析及思路

1.要求逆置链表时，可以创建一个同样长度的链表，即一个一个的加入到新的链表当中，当这样比较浪费空间。由于一个一个的创建节点，然后插入节点，这时空间复杂度为O（n），时间复杂度为O（n），不建议采用该办法。

2.创建链表有头插和尾插法，在给定的链表进行逆置，可以考虑使用头插法，头插法能够快速的将链表逆置，这时不需要创建新的链表，利用原来给定的链表节点即可实现头插法的效果，其空间复杂度为O（1），时间复杂度为O（n）。

头插法过程、源码：

头插法通俗的说头插法插入结点的过程头部一直在变，相对应的尾插法就是尾部一直在变

class Solution {
public:
	ListNode *ReverseList(ListNode*phead)
	{
        if(phead==NULL)//判断该链表是否为空，若为空则返回空
        {
            return NULL;
        }
		ListNode *cur_pointer,*next_pointer;//创建两个结点
		cur_pointer = phead->next;
        phead->next=NULL;
		while(cur_pointer)//检验是否到头
		{  
            next_pointer = cur_pointer->next;//断开之前保存下一个结点
			cur_pointer->next = phead;//当前的指针指向他前面的指针
            phead=cur_pointer;//让头部成为头插法插上的节点
			cur_pointer = next_pointer;//将工具点下移
		}
		return phead;//返回头部
	}
};

测试结果：

参考 1.链表参考：https://www.runoob.com/w3cnote/c-structures-intro.html 2.头插法参考：https://blog.csdn.net/l_jd_gululu/article/details/113621265?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163748807916780274145649%2522%252C%2522scm%2522%253A%252220140713.130102334…%2522%257D&request_id=163748807916780274145649&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2alltop_positive~default-1-113621265.first_rank_v2_pc_rank_v29&utm_term=%E5%A4%B4%E6%8F%92%E6%B3%95&spm=1018.2226.3001.4187