反转链表详解 反转链表图解

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL

输出: 5->4->3->2->1->NULL

这个题是面试中常问到的非常基础的题目，有两种解法，一种是迭代，一种是递归。

迭代：

反转链表的核心其实在于理解链表这种数据结构，如下。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

链表的数据结构是由当前节点值，和下一个节点构成的。而我们反转链表，则需要把当前节点的上一个节点变成他的下一个节点，而把当前节点的下一个节点，变成前一个节点。那这样，我们用迭代的方法，则需要三个两，pre（前一个），cur（当前），next（下一个）。

这样我们在迭代反转链表的时候，记住关键四个步骤：

1.保存当前节点的next节点

2.将cur节点的next节点设置为pre

3.将pre节点的移动到cur节点

4.cur节点移动到刚才保存的next节点

class Solution {
    public ListNode reverseList(ListNode head) {
         ListNode pre = null, cur = head, next = null;
         while(cur != null){
            next = cur.next;//保存下个节点
            cur.next = pre;//下个节点设置为pre
            pre = cur;//pre设置为当前
            cur = next;
         }
         return pre;
    }
}

递归：

递归解题的核心是要有退出递归的条件，同事递归解题的时候，实际上是一个自底向上的过程。那我们就可以把其分解为最简单的 1->2->null ，那么递归终止条件，就是当前节点为null或者是当前节点的next为空就返回。具体值，请看注释。

class Solution {
    public ListNode reverseList(ListNode head) {// 1.传入head 1
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next);//递归传入2，则返回newHead=2节点
        head.next.next = head;// 将newHead的前一个节点head，放到newHead的后一个节点上
        head.next = null// 断开
        return newHead;
    }
}