反转链表 - 简单

*************

C++

topic: 206. 反转链表 - 力扣（LeetCode）

*************

Give the topic an inspection.

It seems really easy. At very first, I think that I will use reverse cammand to kill this topic. But a few seconds later I found that I am strange about list link. So relearn the basic skills about the list link. 

Linked list is a structure. Linked list is used to store data which share the same type. As is known that memary is all to the computer, the linked list donot have to know the size of memory in advance. It has dynamic structure to store the data.

The basic structure of linked list is as follow, just keep it in ur mind.

struct ListNode 
{
    int val;            // 节点存储的值
    ListNode* next;     // 指向下一个节点的指针
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};

Make a linked list 1 -> 2 -> 3

ListNode* head = new ListNode(1);      // 头节点
head->next = new ListNode(2);         // 第二个节点
head->next->next = new ListNode(3);   // 第三个节点

go through linked list.

void printList(Node* head) 
{
    Node* current = head;
    while (current != nullptr) 
    {
        current = current->next;
    }
}

add 0 in the very begin:  0 ->1 -> 2 -> 3

ListNode* newNode = new ListNode(0);
newNode->next = head;  // 新节点指向原头节点
head = newNode;        // 更新头节点
// 链表变为 0 → 1 → 2 → 3

delete 2: 0 ->1 -> 3

ListNode* curr = head;
while (curr->next != nullptr && curr->next->val != 2) 
{
    curr = curr->next;
}
if (curr->next != nullptr) 
{
    ListNode* temp = curr->next;
    curr->next = curr->next->next;  // 跳过待删除节点
    delete temp;                    // 释放内存
}
// 链表变为 0 → 1 → 3

maybe you donot understand why delete the selected node is so camplex, me either. Donot worry about it. I will show me something interesting.

ListNode* head = new ListNode(1);      // 节点1 (val=1)
head->next = new ListNode(2);          // 节点2 (val=2)
head->next->next = new ListNode(3);    // 节点3 (val=3)

head → [1|next] → [2|next] → [3|next] → nullptr

linked list always has head and nullptr, like a zip, head is head, nullptr is end.

if I want to delete ListNode(2), I should find ListNode(1) first.

head → [1|next] → [2|next] → [3|next] → nullptr

// 3. 遍历链表，找到待删除节点的前驱节点
ListNode* curr = head;
while (curr->next != nullptr && curr->next->val != 2) 
{
    curr = curr->next;  // 移动到下一个节点
}

Once ListNode(1) is found, delete 2

// 4. 如果找到待删除节点（curr->next 是节点2）
if (curr->next != nullptr) 
{
    ListNode* temp = curr->next;      // 临时保存节点2的地址
    curr->next = curr->next->next;    // 让节点1直接指向节点3
    delete temp;                      // 释放节点2的内存
}

head → [1|next] → [3|next] → nullptr.

Maybe I will forget how to use the linked list few days later but donot worry, I will learn angain.

Back to the topic.

reverse the linked list, I think make a new linked list, head == nullptr.

/**
 * 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 *previous = nullptr; // 前一个节点，初始化为链表尾部
        ListNode *current  = head; // 当前节点，初始化为链表头
    }
};

reverse\

class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        
        ListNode *previous = nullptr; // 前一个节点，初始化为链表尾部
        ListNode *current  = head; // 当前节点，初始化为链表头

        while (current != nullptr)
        {
            ListNode *nextTemporary = current->next; // 临时变量
            current->next           = previous;
            previous                = current;
            current                 = nextTemporary;
        }

        return previous;
    }
};

for example.

head -> 1 -> 2 -> 3 -> nullptr

prev = nullptr
curr = 1 -> 2 -> 3 -> nullptr

第一次循环：

1. nextTemp = curr->next → 保存节点2的地址
2. curr->next = prev → 节点1的next指向nullptr
3. prev = curr → prev指向节点1
4. curr = nextTemp → curr指向节点2

prev = 1 -> nullptr
curr = 2 -> 3 -> nullptr

第二次循环：

1. nextTemp = curr->next → 保存节点3的地址
2. curr->next = prev → 节点2的next指向节点1
3. prev = curr → prev指向节点2
4. curr = nextTemp → curr指向节点3

prev = 2 -> 1 -> nullptr
curr = 3 -> nullptr

第三次循环

1. nextTemp = curr->next → 保存nullptr
2. curr->next = prev → 节点3的next指向节点2
3. prev = curr → prev指向节点3
4. curr = nextTemp → curr指向nullptr

prev = 3 -> 2 -> 1 -> nullptr
curr = nullptr

#