The title

Title link: leetcode-cn.com/leetbook/re…

Answer key

Research data structure will also appear in the topic ~

1. Invert the linked list using a header interpolation method

Reversing the linked list can be directly traversed the list, and then with an empty node as the head node using the head interpolation method to achieve;

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {

    let vhead = new ListNode(null.null);
    let temp;
    while(head ! = =null) {
        temp = vhead.next;
        vhead.next = head;
        head = head.next;
        vhead.next.next = temp;
    }

    return vhead.next;
};
Copy the code

2, recursive implementation

It is also mentioned in the title that recursion can be used. I did not think of such a deep friendship between linked lists and recursion when I wrote the title of linked lists in C language, so I decided to analyze and check the information to see whether the friendship between linked lists and recursion is stronger than water.

First of all, we know that recursion is mainly composed of recursion body and recursion end condition. When solving a problem, we can turn the whole big problem into a sub-problem with the same logic, so this problem can be solved by recursion (Hannotta problem is a classic problem that can be realized by recursion).

The structure of a linked list is composed of nodes one by one, and each node is the same structure, so the problems related to the list are naturally suitable for recursive implementation;

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */
/ * * *@param {ListNode} head
 * @return {ListNode}* /
var reverseList = function(head) {

    if(head === null || head.next === null) {
        return head;
    }

    

    let rhead = reverseList(head.next); // Recursively returns a reference to the first node of the reversed list

    let next = head.next; // That's the point. Next is the last node in the recursively returned list below;
    next.next = head;
    
    head.next = null; // Remove the loop formed by the first node and the second node before the inversion
                      // head.next === next,next.next === head

    return rhead;
};
Copy the code

Compared with the first method, the use of recursive stack, space for time, is still the law ~


If you have a better way of thinking and reconciliation, welcome to discuss ah ~

This is a summary and implementation of each problem in LeetCode’s “Elementary Algorithms” using JavaScript. The summary is here:

Juejin. Cn/post / 700669…