1. Title Description

Reverse a single linked list. Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

Advancements: You can iterate or recursively reverse linked lists. Can you solve the problem in two ways?

Second, train of thought analysis

Reverse two nodes

It’s hard to start thinking about the inversion of long lists. So it would be much easier to invert a list with only two nodes. Example:

Input:... -> n -> n+1 ->... Output:... -> n+1 -> n ->...Copy the code

Reverse two nodes: just point next of node N +1 to n.

Reverse multiple nodes

So how do you reverse multiple nodes? In fact, you only need to repeat the above operation of reversing the two nodes. Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

The problem solving steps

  1. Use a double pointer to traverse the linked list, two Pointers one before and one after;
  2. In the process of traversing the linked list, the double pointer is constantly reversed

Example:

Input: 1->2->3->4->5->NULL 5->4->3->2->1->NULL // ----- 1 1 2 ^ ^ 1->2->3->4->5->NULL // ----- 2 1 2 ^ ^ 2->1->NULL 3->4->5->NULL // ----- 3 1 2 ^ ^ 3->2->1->NULL 4->5->NULL // ----- 4 1 2 ^ ^ 4->3->2->1->NULL 5->NULL // ----- 5 1 2 ^ ^ 5->4->3->2->1->NULL NULLCopy the code

AC code

Iterative algorithm

var reverseList = function(head) {
    let p1 = null
    let p2 = head

    while(p2) {
        let temp = p2.next
        p2.next = p1
        p1 = p2
        p2 = temp
    }

    console.log(p1)
    return p1
}
Copy the code

A recursive algorithm

var reverseList = function(node, next = null) { if(! node) return null const nodeNext = node.next node.next = next if(nodeNext) { return reverseList(nodeNext, node) } return node }Copy the code

Four,

This problem is actually very simple, but if you start to consider the transformation of the long list will be very complicated and even confusing, so when thinking about the problem do not think too complicated, divide the problem into one after another small problems can be divided and solved. The main test point is the traversal of the linked list and the understanding of the structure of the linked list.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign