NC78 反转链表

解题思路

如题，我们需要做的就是将一个链表反转。那么，我这里有两种做法（当然可能还存在其他的解题思路）。
第一种，即是迭代。next指针保存当前head节点的下一个节点，因为当前head所在的节点即将要指向前面的节点了，如果不用next指针保存的话，那么我们就无法找到后续要反转的节点了。如图。

就这样，一直迭代，每一轮反转以后，我们将当前的head赋值给prev，然后再将next记录的下一个要反转的节点地址赋值给head，这样我们就可以反转整条链表啦。

以下附上我第一种解题思路的代码：

 public ListNode ReverseList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        ListNode prev=null,next;
        while(head!=null){
            next=head.next;
            head.next=prev;
            prev=head;
            head=next;
        }
        return prev;
    }

第二种，即是递归。这个需要一点点递归基础去看懂，即利用递归的特性，从链表的末尾开始反转。

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