This is the 25th day of my participation in Gwen Challenge

Topic describes

Reverse a linked list

Given the head node of a single linked list, reverse the list and return the reversed list. Leetcode-cn.com/problems/re…

Enter: head = [1.2.3.4.5] output: [5.4.3.2.1]
Copy the code

Input: head = [] Output: []Copy the code

The label

recursive

Analysis of the problem solving

1. The iteration

Let’s get right to it.

This question should be in the interview to send points. A little bit of logic.1= >2= >3How to reverse linked lists?1.First store the next, prev for each element.2.Next of each element is then equal to the prev of the previous store. It's easy. Let's write it by hand. In traversal, the traversal element is1Start by recording next = for the current element1= >2Next = for the current elementnullBecause the first element reverses and becomes the reciprocal one, there is no next one to continue iterating, iterating over the element2Again, record next = for the current element2= >3Next of the current element equals the prev of the previous store,..... Until you get to the end of the loop. This topic to speak the truth really dead back all die back down, you go to the interview, in case the interviewer see you like the eye, think you are the son of destiny, immediately give you a reverse chain list as send points, did not play a role!!Copy the code

Go to ！！！！！

/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val? : number, next? : ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */

function reverseList(head: ListNode | null) :ListNode | null {
    // Record the next of the previous element
    let prev = null 
    // head is the first
    let cur = head 

    while (cur) { // When the current element in the traversal exists
        // Record the next of the current element
        const next = cur.next 
        // Change the next of the current element to the previous one
        cur.next = prev 
        // Continue to save
        prev = cur 
        cur = next
    }
    return prev
};

Copy the code

The last

From today not pigeon, every day an algorithm problem and publish an article, first want to solve the problem group for Top100, the thirteenth topic finished work!!