【简单】206. 反转链表

struct ListNode【singly-linked list】

/**
 * 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) {}
 * };
 */

图2-5 单链表结构

单链表的结点结构

typeded struct node{//结构名为node
  T Element;//元素域Element 用户自定义的元素类型T
  struct node* Link;//指针域Link
}Node;//单链表的结点类型Node

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

迭代

/**
 * 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* prev = nullptr;//由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
        ListNode* curr = head;
        while (curr) {//在遍历链表时，
            ListNode* next = curr->next;//在更改引用之前，还需要存储后一个节点。
            curr->next = prev;//将当前节点的 next 指针改为指向前一个节点。
            prev = curr;
            curr = next;
        }
        return prev;//最后返回新的头引用。
    }
};

递归

/**
 * 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) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;//n_{k+1}的下一个节点指向 n_k
        head->next = nullptr;//n_1的下一个节点必须指向∅。如果忽略了这一点，链表中可能会产生环。
        return newHead;
    }
};