206. Reverse Linked List

1.recursion:

分为三步：定义递归函数以及它的input，考虑递归关系(改指针)，设定返回条件(cur为null的时候返回pre)

public ListNode reverseList(ListNode head) {
    return dfs(null, head);
}

public ListNode dfs(ListNode pre, ListNode cur) {
    if (cur == null) return pre;
    ListNode next_node = cur.next;
    cur.next = pre;
    return dfs(cur, next_node);
}

2.iteration:

四步见图

def reverseList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    pre = None
    while head:
        next_node = head.next
        head.next = pre
        pre = head
        head = next_node
    return pre