[leetcode] reverse linked list

#LeetCode A daily topic 【 Special topic of linked list 】

• Reverse a linked list
  https://leetcode-cn.com/problems/reverse-linked-list/

• analysis
  Here's the head node of the list head , Please reverse the list , And return the inverted linked list .
  1——>2——>3——>4——>5
  become
  5——>4——>3——>2——>1

• Realization

Non recursive ： Node by node processing , Record the location of the previous node and the location of the next node , Set the... Of the current node next Point to the previous node

	public ListNode reverseList(ListNode head) {
    
        //  Reverse a linked list 
        ListNode prev = null, next;
        while (head != null) {
    
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
       return prev;
    }

LeetCode Time consuming ：0ms

recursive ： The principle is the same , Set the... Of the current node next Point to the previous node

	public ListNode reverseList(ListNode head) {
    
        return reverse(head,null);
    }
    /*  Use recursion to reverse the linked list  */
    public ListNode reverse(ListNode head, ListNode prev) {
    
        if (head == null) {
    
            return prev;
        }
        ListNode next = head.next;
        head.next = prev;
        return reverse(next, head);
    }

LeetCode Time consuming ：0ms

• summary ：
  Traversal is good at solving problems from the front to the next , Sometimes I want to use recursion to realize traversal , It is often necessary to add a parameter to record the results of operations from front to back ;
  However, recursion is often used in , Recursion to the deepest point requires some operations , And then add up , I.e. upward tracing .