参考：https://blog.csdn.net/superxiaolong123/article/details/86687733
首先要了解一个链表节点的数据结构：
value代表该节点存储的值，next指向下一个节点，next可能指向一个单一节点，也可能指向一个链表，也可能指向null(代表尾节点)。
方法一：头节点插入法(推荐)
实现步骤：
- 创建一个带头节点的链表resultList
- 定义一个循环链表变量p，p的初始值为待反转的链表
- 遍历待反转的链表，遍历条件为 (p !=null)
3.1 定义一个临时链表变量tempList保存p->next的值（因为p->next值会改变），用于下一次循环。
3.2 把p当前指向的首节点和resultList链表的头节点之后的节点拼接起来。（resultlist.next其实=null,相当于把插入节点的next置为null，等价于p.next = null）
3.3 把3.2步骤中拼接的节点 再拼接到resultList头节点后。
3.4 p重新赋值为3.1步骤中保存的tempList的值。 - 返回resultList->next.即反转后的链表。
图解：
图1就是待反转的原始链表，图2是 带头节点的链表resultList。
可以看到p是一个循环变量，初始值指向待反转的原始链表。
通过p变量遍历链表，在遍历中（列举的值为第一次循环的情况）：
- 定义一个临时链表变量tempList保存p->next的值，tempList指向图1.2
- 把p当前指向的首节点(图1.1)和resultList链表的头节点之后的节点（图2.2）拼接起来。
- 把3.2步骤中拼接的节点(图3.2) 再拼接到resultList头节点后。
- p重新赋值为3.1步骤中保存的tempList的值，即图1.2。
最后返回resultList->next，也就是去除了头节点-1的值。
通过头结点插入法实现链表反转功能，主要难点就是在循环中的3.2和3.3步骤的理解。
需要注意的是，就是关注循环变量p的值，也就是指向的变化，传统的遍历过程就是条件为p!=null,处理,p=p->next。但是在这个头结点插入代码中，p->next的值发生的变化，因为要将resultList结果链表的内容拼接到p的首节点后，所以要定义一个临时变量存p->next。
public static ListNode reverseListByInsert(ListNode listNode){
//定义一个带头节点的
ListNode resultList = new ListNode(-1);
//循环节点
ListNode p = listNode;
while(p!= null){
//保存插入点之后的数据
ListNode tempList = p.next;
p.next = resultList.next;//连接头节点和下一个节点（参照头插法图）
resultList.next = p;
p = tempList;
}
return resultList.next;
}
逻辑参考2
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
ListNode* reverseList(ListNode* head) {
ListNode *phead=new ListNode(-1);//注意第6行listNode(int x)中括号要写值，这里随便写，因为头节点的val不重要
phead->next=NULL;//申请一个头节点，在空结点后插入值
ListNode *ptemp;//临时结点，存放插入的值
ListNode *t;//控制插入节点的值
t=head;//从第一个结点开始
while(t!=NULL){
ptemp=t;
t=t->next;
ptemp->next=phead->next;//phead->next第一次其实=null
phead->next=ptemp;
}
return phead->next;
}
方法二：就地反转1
头结点插入法的实质是重新创建了一个新的链表，通过遍历待反转链表，将链表每一个节点插入到创建的链表中，然后的到的这个创建的链表就是反转后的链表。而就地反转实质就是在待反转链表基础上修改节点顺序得到反转链表。所以原理还是不同的。
图解：
个人认为就地反转比头结点插入稍微难理解一点。
宏观上来看，要实现节点1和节点2反转，需要将节点1插入节点2和节点3当中，然后将头节点为2的链表插入结果链表头结点后面，然后再后移一个节点做同样的操作。
然而涉及到两个节点的循环赋值，这个操作顺序就比较重要了。
正确的步骤是先将节点2切分出来，再将节点2插入-1和1之间。
实现步骤
- 创建一个带头节点的链表resultList，头结点指向待反转的链表。
- 创建p、pNext两个用于循环操作，分别指向两个待反转节点的位置,初始值如图所示，指向1和2
- 遍历带反转的链表，循环条件是pNext!=null.
3.1 从链表中分割出pNext节点，也就是让p指向pNext->next。
3.2 让pNext指向经过3.1操作之后的resultList.next（1->3->4->5）
3.3 让resultList头结点指向pNext(2->1->3->4->5)
3.4 让pNext指向p的下一个节点
难点在于理解循环中resultList.next指向性的变化，以及p和pNext两个变量的变化，p指向的链表首结点永远是1,只是节点1在resultList链表中位置在发生变化，而pNext是随着p移动的，脑子中间可以有一个摆绳模型，在起始点位置发力，绳子的高点位置会移到绳尾，那个最高点就是p变量位置。
public static ListNode reverseListByLocal(ListNode listNode){
ListNode resultList = new ListNode(-1);
resultList.next= listNode;
ListNode p = listNode;
ListNode pNext = p.next;
while (pNext!=null){
p.next = pNext.next;
pNext.next = resultList.next;
resultList.next = pNext;
pNext=p.next;
}
return resultList.next;
}
头插法分析图：
方法二：就地反转2(推荐)
参考：https://www.cnblogs.com/byrhuangqiang/p/4311336.html
2.1 思路
把当前链表的下一个节点pCur插入到头结点dummy的下一个节点中，就地反转。
dummy->1->2->3->4->5的就地反转过程：
dummy->2->1->3->4->5
dummy->3->2->1->4->5
dummy->4>-3->2->1->5
dummy->5->4->3->2->1
2.2 解释
1初始状态
2 过程
pCur是需要反转的节点。
- prev连接下一次需要反转的节点
- 反转节点pCur
- 纠正头结点dummy的指向
- pCur指向下一次要反转的节点
伪代码
1 prev.next = pCur.next;
2 pCur.next = dummy.next;
3 dummy.next = pCur;
4 pCur = prev.next;
3 循环条件
pCur is not null
2.3 代码
// 1.就地反转法
public ListNode reverseList1(ListNode head) {
if (head == null)
return head;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev =head;//修改了原文的dummy.next
ListNode pCur = prev.next;
while (pCur != null) {
prev.next = pCur.next;
pCur.next = dummy.next;
dummy.next = pCur;
pCur = prev.next;
}
return dummy.next;
}
2.4 总结
- 1个头结点，2个指针，4行代码
- 注意初始状态和结束状态，体会中间的图解过程。
