算法篇1反转链表

一、描述

给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O*(1) ，时间复杂度O(*n) 。

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

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

以上转换过程如下图所示：

示例1

输入：{1,2,3}

返回值：{3,2,1}

示例2

输入：{}

返回值：{}

说明： 空链表则输出空

二、题目解析

反转链表是非常经典的一道算法题，它的解法非常之多，而递归、迭代是我们最需要掌握的两种，其中递归的代码非常简洁，但很难理解。

我们再来回顾一下递归的模板，终止条件，递归调用，逻辑处理。

public ListNode reverseList(参数0) {
    if (终止条件)
        return;

    逻辑处理（可能有，也可能没有，具体问题具体分析）

    //递归调用
    ListNode reverse = reverseList(参数1);

    逻辑处理（可能有，也可能没有，具体问题具体分析）
}

终止条件就是链表为空，或者是链表没有尾结点的时候，直接返回

if (head == null || head.next == null)
    return head;

递归调用是要从当前节点的下一个结点开始递归。逻辑处理这块是要把当前节点挂到递归之后的链表的末尾，看下代码

import java.util.*;

//建节点
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        // write code here
        //终止条件
        if(head == null || head.next == null){
        return head;
}
		//cur到5后返回head=4
		ListNode cur = ReverseList(head.next);
		//head的下下节点指向前一个
		head.next.next = head;
		//head=4本来指向5，现在断开了指向空
		head.next = null;
		
		return cur
    }
    
}