算法训练营第六天|反转链表

题目链接： https://leetcode.cn/problems/reverse-linked-list/

视频链接：https://www.bilibili.com/video/BV1nB4y1i7eL

难点：迭代中如何防止断链以及递归如何实现反转 感想：写的时候容易忽略指针丢失的问题

思路：反转链表就是让每个节点的next指向前一个节点 最直观的想法是遍历链表 一边走一边改变指向 需要一个prev记录前驱 一个curr记录当前节点 用一个临时变量报错curr->next防止断链

迭代法:如果不保存curr->next一旦修改curr->next就丢失了后续节点

递归法:假设head->next之后的链表已经反转完毕 返回的新头是newHead 此时head->next变成了反转后链表的尾节点 所以head->next->next=head把当前节点接到尾部 head->next=NULL断开旧连接 避免成环