使用递归方式解决“链表反转”问题

题目：反转链表
详细描述：给定一个单链表的头结点pHead(这个头节点是有值的，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围：0 ≤ n ≤ 1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
例如：如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

转换过程如下图所示：

示例1
输入：{1,2,3}，返回值：{3,2,1}
示例2
输入：{}，返回值：{}

解法2：
递归：以相似的方法重复，类似于树结构，先从根节点找到叶子节点，从叶子节点开始遍历大的问题(整个链表反转)拆成性质相同的小问题(两个元素反转)curr.next.next = curr。将所有的小问题解决，大问题即解决。
步骤：
1、只需每个元素都执行以下两个步骤即可：
curr.next.next = curr
curr.next = null
2、为了保证链不断，必须从最后一个元素开始

package od;

/**
 * 使用迭代方式解决“链表反转”问题
 * 题目：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
 * 原文地址：https://www.codernav.com/2778.html
 */
public class OdTest05 {
    static class ListNode {
        int val;
        OdTest04.ListNode next;

        public ListNode(int val, OdTest04.ListNode next) {
            this.val = val;
            this.next = next;
        }

    }

    public static void main(String[] args) {
        // node1 -> node2 -> node3 -> node4 -> node5
        OdTest04.ListNode node5 = new OdTest04.ListNode(5, null);
        OdTest04.ListNode node4 = new OdTest04.ListNode(4, node5);
        OdTest04.ListNode node3 = new OdTest04.ListNode(3, node4);
        OdTest04.ListNode node2 = new OdTest04.ListNode(2, node3);
        OdTest04.ListNode node1 = new OdTest04.ListNode(1, node2);
        OdTest04.ListNode prev = f(node1);
        System.out.println(prev);
    }

    /**
     * 递归方式
     * @param head
     * @return
     */
    public static OdTest04.ListNode f(OdTest04.ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 递归的目的是找到最后一个元素，从后往前执行下面的算法，如果从前往后执行，会导致执行一次算法后，链接断开
        OdTest04.ListNode newHead = f(head.next);
        // 将后一个节点的next节点指向head
        head.next.next = head;
        // 将后一个节点指向null
        head.next = null;
        return newHead;
    }
}

测试：在方法前后分别打断点，查看ListNode里的值。

反转前：ListNode的顺序是1>2>3>4>5

反转后：ListNode的顺序是5>4>3>2>1