/**
 * @Author:田宇寒.
 * @Date:Created in 14:45 2021年6月3日
 * @Description:反转链表
 * @ModifiedBy:
 * @Version: 1.0
 */
public class code206 {

 public class ListNode {
 int val;
 ListNode next;

 ListNode() {
 }

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

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

 class Solution {
 public ListNode reverseList(ListNode head) {
 /**
 * create by: 田宇寒
 * description: 递归解法 时间复杂度O(n)空间复杂度O(n)
 * create time: 14:56 2021年6月3日
 * @Param: head
 * @return code206.ListNode
 */
 if (head == null || head.next == null) {
 return head;
 }
 ListNode newHead = reverseList(head.next);
 head.next.next = head;
 head.next = null;
 return newHead;
 }
 }

 class Solution2 {
 public ListNode reverseList(ListNode head) {
 /**
 * create by: 田宇寒
 * description: 迭代算法 时间复杂度O(n) 空间复杂度O(1)
 * create time: 14:56 2021年6月3日
 * @Param: head
 * @return code206.ListNode
 */
 ListNode current = head;
 ListNode prev = null;
 while (current != null) {
 ListNode next = current.next;
 current.next = prev;
 prev = current;
 current = next;
 }
 return prev;
 }
 }
}