剑指Offer面试题：18.反转链表
一、题目
————————————————
题目描述
输入一个链表，反转链表后，输出新链表的表头。
————————————————
二、思路
————————————————
要求很简单，输入一个链表，反转链表后，输出新链表的表头。
反转链表是有2种方法(递归法，遍历法)实现的，面试官最爱考察的算法无非是斐波那契数列和单链表反转，递归方法实现链表反转比较优雅，但是对于不了解递归的同学来说还是有理解难度的。
方法一：递归法
总体来说，递归法是从最后一个Node开始，在弹栈的过程中将指针顺序置换的。
为了方便理解，我们以 1->2->3->4这个链表来做演示。输出的效果是4->3->2->1
方法二：遍历法
遍历法就是在链表遍历的过程中将指针顺序置换
致敬作者：上帝爱吃苹果
致敬链接：https://www.cnblogs.com/keeya/p/9218352.html
致敬博主：决定我们心情的不止是现在这个时候我们所拥有的，更是我们对未来的预期。
————————————————
三、解决问题
————————————————
测试算例
1.功能测试（链表有多个或一个结点）
2.特殊测试（头结点为null）
————————————————
package swordoffer;
/**
* @author LQ
* @version 1.0
* @date 2020-03-23 15:50
*/
import java.util.List;
/**
* 题目：
* 输入一个链表，反转链表后，输出新链表的表头。
* 为了方便理解，我们以 1->2->3->4这个链表来做演示。输出的效果是4->3->2->1
*/
public class Solution18 {
public static void main(String[] args) {
Solution18 demo = new Solution18();
System.out.println("==============================");
System.out.println("递归test1");
demo.test1();
System.out.println("==============================");
System.out.println("递归test2");
demo.test2();
System.out.println("==============================");
System.out.println("遍历法test1");
demo.test3();
System.out.println("==============================");
System.out.println("遍历法test2");
demo.test4();
System.out.println("==============================");
}
//1.递归
//递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场。
public ListNode ReverseList01(ListNode head) {
if(null == head || null == head.next){
return head;
}
ListNode temp = head.next;
//进入递归
//我们假设此时递归到了3结点，此时head=3结点，temp=3结点.next(实际上是4结点)
//执行ListNode newHead = ReverseList01(head.next);传入的head.next是4结点，返回的newHead是4结点。
ListNode newHead = ReverseList01(head.next);
//接下来就是弹栈过程了
temp.next = head;//程序继续执行 temp.next = head就相当于4->3
head.next = null;//head.next = null 即把3结点指向4结点的指针断掉。
return newHead;//返回新链表的头结点newHead
//注意：当retuen后，系统会恢复2结点压栈时的现场，此时的head=2结点；temp=2结点.next(3结点)，再进行上述的操作。最后完成整个链表的翻转
}
//2.遍历法就是在链表遍历的过程中将指针顺序置换
//依旧是1->2->3->4
public ListNode ReverseList02(ListNode head) {
//1、准备两个空结点 pre用来保存先前结点、next用来做临时变量
ListNode pre = null;
ListNode cur = null;
while(head != null){//6、进行下一次循环head=2结点
cur = head.next;//2、在头结点head遍历的时候此时为1结点 6.1、 cur = 2结点.next(3结点)
head.next = pre;//3、1结点.next=pre(null) 6.2、2结点.next=pre(1结点)=>即完成2->1
pre = head;//4、pre = 1结点 6.3、pre = 2结点
head = cur;//5、head = 2结点 6.4、head = 3结点 进行循环...
}
return pre;
}
//=====================测试代码=======================
/*
* 1.功能测试（链表有多个或一个结点）
*/
void test1() {
ListNode head1=null;
ListNode result1=ReverseList01(head1);
if (null == result1){
System.out.println("result为null");
}else{
while(result1 != null){
System.out.print(result1.val + " ");
result1 = result1.next;
}
}
}
/*
* 2.特殊测试（头结点为null）
*/
void test2() {
ListNode head1=new ListNode(1);
ListNode node2=new ListNode(2);
ListNode node3=new ListNode(3);
ListNode node4=new ListNode(4);
head1.next=node2;
node2.next=node3;
node3.next=node4;
ListNode result1=ReverseList01(head1);
if (null == result1){
System.out.println("");
}else{
while(result1 != null){
System.out.print(result1.val + " ");
result1 = result1.next;
}
}
System.out.println();
}
/*
* 1.功能测试（链表有多个或一个结点）--方法二：遍历法
*/
void test3() {
ListNode head1=null;
ListNode result1=ReverseList02(head1);
if (null == result1){
System.out.println("result为null");
}else{
while(result1 != null){
System.out.print(result1.val + " ");
result1 = result1.next;
}
}
}
/*
* 2.特殊测试（头结点为null）--方法二：遍历法
*/
void test4() {
ListNode head1=new ListNode(1);
ListNode node2=new ListNode(2);
ListNode node3=new ListNode(3);
ListNode node4=new ListNode(4);
head1.next=node2;
node2.next=node3;
node3.next=node4;
ListNode result1=ReverseList02(head1);
if (null == result1){
System.out.println("");
}else{
while(result1 != null){
System.out.print(result1.val + " ");
result1 = result1.next;
}
}
System.out.println();
}
}
————————————————
努力也是需要学习的，别再让你的努力，只感动了自己！愿你的每一次努力，都能为自己和别人创造价值。
Java基础 文章被收录于专栏
建立本人的Java基础技术栈积累库
