进阶：反转链表2（指定l，r）

    2. /**
    3.  * Definition for singly-linked list.
    4.  * struct ListNode {
    5.  *     int val;
    6.  *     ListNode *next;
    7.  *     ListNode(int x) : val(x), next(NULL) {}
    8.  * };
    9.  */
    10. //1. 迭代-----头插法1
    11. class Solution {
    12. public:
    13.     ListNode* reverseList(ListNode* head) {
    14.         ListNode *prev = nullptr;
    15.         ListNode *cur = head;
    16.         while(cur){
    17.             ListNode *next = cur->next;
    18.             cur->next = prev;
    19.             prev = cur;
    20.             cur = next;
    21.             /*
    22.             思路：54321变成12345，后继都变成前驱，所以可以使后继指向自身，之后指针cur后移
    23.             */
    24.         }
    25.         return prev;
    26.     }
    27. };
    28. //2. 迭代---就地逆置
    29. class Solution {
    30. public:
    31.     ListNode* reverseList(ListNode* head) {
    32.         if(!head || !head->next) return head;
    33.         auto l = head;
    34.         auto r = l->next;
    35.         while(r){
    36.             auto next = r->next;
    37.             r->next = l;
    38.             l = r;
    39.             r = next;
    40.         }
    41.         head->next = NULL;
    42.         return l;
    43.     }
    44. };
    46. //3. 递归
    47. class Solution {
    48. public:
    49.     ListNode* reverseList(ListNode* head) {
    50.        if(!head || !head->next) return head;
    51.        ListNode *cur = reverseList(head->next);
    52.        head->next->next = head;
    53.        head->next = nullptr;
    54.        return cur;
    55.     }
    56. };
    57. //4. 迭代,头插法2
    58. class Solution {
    59. public:
    60.     ListNode* reverseList(ListNode* head) {
    61.         //迭代,头插法
    62.         ListNode *dummy = nullptr;
    63.         ListNode *cur = head;
    64.         while(cur){
    65.             ListNode *next = cur->next;
    66.             if(!dummy) {
    67.                 dummy = cur;
    68.                 dummy->next = NULL;
    69.             }else{
    70.                 cur->next = dummy;
    71.                 dummy = cur;
    72.             }
    73.             cur = next;
    74.         }
    75.         return dummy;
    76.     }
    77. };

    递归理解自链接
    image.png