Amazon-Reverse Linked List (Easy

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution:

    public ListNode reverseList(ListNode head) {
        if(head==null||head.next==null) return head;
        /*
        ListNode pre=null;
        ListNode cur=head;
        while(cur!=null){
            
            ListNode next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
        */
        
        ListNode newHead=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
        
    }

时间复杂度：O(n)
空间复杂度：O(1)/O(n) （递归）

递归思路，找到链表最后一个节点，返回，此时head指向前一个节点，将head的next节点指向head，head断链，返回新的头结点
迭代思路，三个指针，每次反转操作使用cur.next指向pre，依次迭代，不能用next作为判断结束，所以next要在迭代里创建，因为用next指针判断会造成最后一个节点无法反转，或在循环外进行单独反转。