Topic describes

Given the head node of a single linked list, reverse the list and return the reversed list.

Given: 1 -> 2 -> 3 -> 4 -> 5

Return: 5 -> 4 -> 3 -> 2 -> 1

code

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; * /
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        ListNode *pre = nullptr, *curr = head, *next = nullptr;

        while(curr ! =nullptr) {
            next = curr->next;
            curr->next = pre;
            // The pre and curr nodes are one step behind each other
            pre = curr;
            curr = next;
        }
        returnpre; }};Copy the code

Their thinking

The initial state

The initial state just needs to bepreandnextThe node tonullptr.currThe node toheadNode.

Cycle steps

The first step we need to do is savecurrThe next node of a node for subsequent usecurrThe node is moved one step back.

Reverse curr to the pre node.

  1. The tail node after the inversion should point tonullptr, sopreThe initial node isnullptr.
  2. Records are required before inversioncurrNext node, so thatcurrNext move back.

whencurrAfter reversing the pointing direction, the firstpreThe node tocurrThe current position is equivalent topreThe node moves back one step.

At this point, point the curr node to the next node to complete the backward step.

The whole process