【剑指24】单链表反转

题目描述

输入一个链表，反转链表后，输出新链表的表头。

代码

    //1.递归
    public ListNode ReverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = head;
        ListNode next = head.next;
        pre.next = null;
        ListNode retrunNode = ReverseList(next);
        next.next = pre;
        return retrunNode;
    }

    //2.迭代
    public ListNode ReverseList2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode pre = head;
        ListNode next = head.next;
        while (next != null) {
            ListNode temp = next.next;
            next.next = pre;
            pre = next;
            next = temp;
        }
        head.next = null;
        return pre;
    }