C++ 刷题笔记_9 反转链表

提示：力扣第206题

题目：

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

示例：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解题思路：

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表。
使用双指针：指针cur从head一直遍历到尾部->next，另一指针 pre = cur，改变指针的方向即可，详细的见代码。

题解：

代码如下（示例）：

#include<iostream>
#include<vector>

using namespace std;
/*反转链表*/
//定义节点
struct LinkedNode{
    int val;
    LinkedNode *next;
    LinkedNode(int x):val(x),next(nullptr){}
    LinkedNode(int x,LinkedNode *next):val(x),next(next){}
};

class Solution{
public:
//反转函数
    LinkedNode *reverseList(LinkedNode *head){
        LinkedNode *temp;//定义temp来保存接下来要反转的节点
        LinkedNode *cur = head;//定义cur=head遍历
        LinkedNode *pre = NULL;
        while(cur)
        {
            temp = cur->next;//保存节点
            cur->next = pre;//改变指向
            pre = cur;//pre向前移动
            cur = temp;//cur向前移动
        }
        return pre;//返回新的头节点
    }
   
// 打印链表
    void printLinkedList(LinkedNode *head) {
        LinkedNode *cur = head;
        while (cur != nullptr) {
            cout << cur->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

};

int main(void)
{
    Solution k;
    LinkedNode *tail = new LinkedNode(1);
    LinkedNode *c = new LinkedNode(2,tail);
    LinkedNode *b = new LinkedNode(3,c);
    LinkedNode *a = new LinkedNode(4,b);
    k.printLinkedList(a);//打印以a为头结点的链表：4，3，2，1
    LinkedNode *res = k.reverseList(a);//反转链表
    k.printLinkedList(res);//打印反转后的链表
}

运行结果：

总结

这是对链表的简单操作，反转链表的核心是改变每个节点的指针指向。