The title

Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list. Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Limit: 0 <= Number of nodes <= 5000

Train of thought

Double pointer

Choose the double-pointer iterative method.

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; * /
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p = head,*pre = NULL;
        
        while(p) {
            ListNode *temp = p->next;// hold the successor of the current node
            p->next = pre;
            // Double pointer moves backwards simultaneously
            pre = p;
            p =temp;
        }
        returnpre; }};Copy the code

This can be done by traversing the chat table, using the pre pointer to point to the node above the current node, and changing the pointer to point to the node with pre’s poop.

  1. Use the temp pointer to store the successor of the current node P
  2. The current node P points to pre which is the precursor of the current node P (initially null)
  3. Pre and P move backwards together
  4. So the last time we move back,p points to nothing,pre points to the last node, so just return pre

A picture can be easily understood:

recursive

The recursion is essentially the same as the previous method, but he does it recursively

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; * /
class Solution {
public:

    ListNode* df(ListNode *p,ListNode *pre) {
        if(p == NULL) return pre;
        ListNode *temp = p->next;// save the successor of p
        p->next = pre;
        return df(temp,p);
    }

    ListNode* reverseList(ListNode* head) {
        return df(head,NULL);ListNode* cur = head,*pre = NULL; ListNode* cur = head,*pre = NULL;}};Copy the code

Use a recursive function to recurse all the way to the end of the list, which is the inverted head, Pre, changing the direction of the pointer each time. Or you could recursively find the node, and then start at the end of the list and change the direction of the pointer at each level of recursion, so the recursion would be different.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return df(head, NULL);           // call recursion and return
    }
    ListNode* df(ListNode *p, ListNode *pre) {
        if (p == NULL) return pre;        // Termination conditions
        ListNode* temp = df(p->next, p); // Recursive successor nodes
        p->next = pre;// Change the node reference point
        return temp;// Return the head node of the reverse list}};Copy the code