反转链表.md

反转链表

题目描述

时间限制：1秒

空间限制：32768K

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

解题思路

一、递归

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

二、头插法-迭代

public ListNode ReverseList(ListNode head) {
    ListNode newList = new ListNode(-1);
    while (head != null) {
        ListNode next = head.next;
        head.next = newList.next;
        newList.next = head;
        head = next;
    }
    return newList.next;
}