企业官网建设流程全解析

法（一） new新结点

这个题直觉就是，一边从head节点读原链表，一边从尾结点生成新链表。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode lastOne = null; //上一个生成的结点 ListNode newNode = null; //新生成的结点 while (head != null) { newNode = new ListNode(head.val); newNode.next=lastOne; lastOne = newNode; head = head.next; } return newNode; } }

当然，还能想到一个脑回路更简单（大脑更喜欢）的方式，先遍历一遍原链表，把值存到数组里，然后倒序遍历数组，从头节点开始生成新链表。这两种方法都需要new，空间复杂度一个是O(n)，一个是O(2n）

法（二）不用new新节点

链表题一定要画图哦，这个题是三指针。

先看三个指针都在链表中间的普通情况，能写出以下递推关系：

now.next=pre; pre=now; now=next; next=next.next;

再看①只有两个结点时 ②走到尾结点的时候 这两种情况，根据这两种情况写出退出循环的条件。

if(now!=null) next=next.next; else break;

完整代码：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { //特殊情况 if(head==null) return null; //特殊情况 if(head.next==null){ return head; } ListNode pre = head; ListNode now = head.next; ListNode next = now.next; //新的处理尾结点.next=null pre.next=null; while(true){ now.next=pre; pre=now; now=next; if(now!=null) next=next.next; else break; } return pre; } }

法（二）递归

法（一）就是最简单的做法了，别问为什么，是进阶要求。

递归出口：依然按照我的一贯用例，第n轮出来。再提醒一下是否是第n轮出来看的是你递归出口的判断if(xxx==null)写在整个方法的最前面，可别理解成了root==null就是第n轮，root.next==null就是提前一轮出来。

递归方法定义：很简单，因为跟原题的要求一样。定义reverseList(head)：把head为头结点的链表反转过来。因为跟原题要求的一样，所以不用重写方法，题目给的reverseList方法就可以是我们的递归方法。

递推关系的语义表达：把head为头结点的链表反转过来，相当于把head后面的所有结点翻转过来，然后反转结果的尾结点指向head，head的next再指向null。

根据语义表达写出递推公式：

ListNode head后面所有结点的反转结果behindList= reverseList(head.next);

//找到反转结果的尾结点

while(behindList!=null){ behindList=behindList.next;}

//反转结果的尾结点指向head

behindList.next=head;

//head指向null

head.next=null;

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { //特殊情况，非递归出口。 if(head==null) return null; //递归出口 if(head.next==null){ return head; } ListNode behindList = reverseList(head.next); ListNode temp = behindList; //得到尾结点 while(temp.next!=null){ temp=temp.next; } temp.next = head; head.next=null; return behindList; } }

当子方法翻转完，处理结点之间连接的时候，除了我上面那种简单的（大脑喜欢的）方式。还有一种写法。

以原链表是1->2->3->4，head是1为例。2->3->4反转后尾结点是2，而反转前的head.next就是2，现在head.next.next就表示尾结点2的next要连接什么，连接反转前的头结点呀!也就是head.next.next=head；