反转链表

描述

输入一个长度为n链表，反转链表后，输出新链表的表头。
数据范围 n <= 1000
要求：空间复杂度 O(1) ，O(n) 。

示例1

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

示例2

输入：{}
返回值：{}
说明：空链表则输出空

Java 真正的递归

package com.practices.practice001.a003;

public class Main {
    public static void main(String[] args) {
        ListNode li =
                new ListNode(1,
                        new ListNode(2,
                                new ListNode(3,
                                        new ListNode(4,
                                                new ListNode(5,
                                                        new ListNode(6)
                                                )
                                        )
                                )
                        )
                );

        System.out.println(li);

        Solution solution = new Solution();

        ListNode rs = solution.ReverseList(li);

        System.out.println(rs);
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

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

    @Override
    public String toString() {
        return val + " " + (next == null ? "" : next);
    }
}


class Solution {

    private int count = 0;

    public ListNode ReverseList(ListNode head) {
        return head == null ? null : reverse(head, head.next);
    }

    private ListNode reverse(ListNode prev, ListNode curr) {
        if (prev == null) return null;
        if (count == 0) prev.next = null;
        count++;
        if (curr != null) {
            ListNode realNext = curr.next;
            curr.next = prev;
            return reverse(curr, realNext);
        } else {
            return prev;
        }
    }
}

Java 精简后的代码

package com.practices.practice001.a003;

public class Main {
    public static void main(String[] args) {
        ListNode li =
                new ListNode(1,
                        new ListNode(2,
                                new ListNode(3,
                                        new ListNode(4,
                                                new ListNode(5,
                                                        new ListNode(6)
                                                )
                                        )
                                )
                        )
                );

        System.out.println(li);

        Solution solution = new Solution();

        ListNode rs = solution.ReverseList(li);

        System.out.println(rs);
    }
}

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

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

    @Override
    public String toString() {
        return val + " " + (next == null ? "" : next);
    }
}


class Solution {

    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode res = ReverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }

}