太原适合网站设计地址,小型个人网站制作,郑州嵌入式培训机构,wordpress大学视频教程题目 反转一个单链表。
示例:
输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题#xff1f;
迭代双指针
从某公众号#xff08;代码随想录#xff09;搬过来的gif图2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题
迭代双指针
从某公众号代码随想录搬过来的gif图看了能很好地理解转置的过程
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* pre nullptr;ListNode* cur head;ListNode* tmp;while(cur ! NULL){//临时结点暂存当前节点的下一个节点用于后移tmp cur-next;//当前节点指向它前面的节点完成转置cur-next pre;//前指针后移pre cur;//当前指针后移cur tmp;}return pre;}
};递归解
递归思路 递归动态图 主要思路 head 的下一个节点指向head 具体实现步骤过程见 https://leetcode-cn.com/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
递归模板;
class Solution {
public:ListNode* reverseList(ListNode* head) {//终止条件//终止条件是当前节点或者下一个节点null//终止条件为何是这个第一个head是null防止一开始传入的就是空指针//若一开始传入的就是空指针则会返回空指针//若一开始传入的是headnull则会直接返回head//若一开始传入的是headnode2...null,则正常递归返回if(head NULL || head-next NULL){return head;}//调用递归逻辑//在函数内部改变节点的指向也就是 head 的下一个节点指向 head 递归函数ListNode* cur reverseList(head-next);head-next-next head;//防止链表循环需要将head.next设置为空此时原来的head变为尾部head-next NULL;return cur;}
};
