前言

记录八:力扣【206.反转链表】
继续


一、题目阅读

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表
示例 1:
在这里插入图片描述

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

示例 2:
在这里插入图片描述

输入:head = [1,2]
输出:[2,1]

示例 3:

输入:head = []
输出:[]

提示:

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶

链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?

二、 第一次尝试

思路:反转链表,就是要改变节点指针指向它前一个节点。

  • 假设cur指向当前要改变方向的节点,即目标。
  • 第一:我需要记录cur前一个节点,用pred指向。因为单向链表,如果没有pred记录位置,无法反向找到;
  • 第二:我需要记录cur后一个节点,用succ指向。因为cur->next改变,如果没有succ记录位置,链表就断开,无法继续操作。

所以我多定义了指针,帮助记录位置,代码部分如下:

//通过测试。
/**
 * 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* dummy_node = new ListNode(0,head);	//虚节点
        ListNode* cur = dummy_node->next;//改变指针方向的节点
        ListNode* pred = dummy_node;//记录cur的前一个节点
        ListNode* succ = nullptr;//记录cur的后一个节点

        while(cur != nullptr){	//因为要获得cur->next,所以cur不能为空
            succ=cur->next;
            cur->next = pred;	//改变方向。
            pred = cur;			//指针后移
            cur = succ;
        }
	//出while循环时,cur是空,pred是原链表的最后一个节点
        head->next = cur;	
        head = pred;	//更改head,返回新链表的头
        delete dummy_node;	//删除虚节点
        return head;	//得到返回值
    }
};

逻辑检查:用一些边界例子带入尝试

  • 当传入head=nullptr是空链表时,不进入while循环,但是head->next = cur;操作了head空指针。所以需要补充if(head == nullptr)情况
  • 当传入只有一个节点时,while结束后的语句符合逻辑,可以统一。

总结,完整代码如下,通过测试:

/**
 * 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 == nullptr){
            return head;
        }
        ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = dummy_node->next;//改变指针方向的节点
        ListNode* pred = dummy_node;//记录cur的前一个节点
        ListNode* succ = nullptr;//记录cur的后一个节点

        while(cur != nullptr){
            succ=cur->next;
            cur->next = pred;
            pred = cur;
            cur = succ;
        }

        head->next = cur;//此时cur是空
        head = pred;
        delete dummy_node;
        return head;

    }
};

尝试迭代

尝试简洁代码,用迭代实现,尝试用迭代调用实现,reverseList过程在函数内再次调用就是迭代。
没想出来流程。
目标——学习迭代。


三、代码随想录

学习内容

  • 双指针法:
    其实就是二、总结出的代码,但是我的代码有几行多余,可是改成参考版本就简洁一些:
/**
 * 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 == nullptr){	检查逻辑后,发现while可以包含所有情况,不用这个if判断。
        //    return head;
        //}
        //ListNode* dummy_node = new ListNode(0,head);
        ListNode* cur = head;//改变指针方向的节点
        ListNode* pred = nullptr;//记录cur的前一个节点
        ListNode* succ = nullptr;//记录cur的后一个节点

        while(cur != nullptr){	//while内不用改
            succ=cur->next;
            cur->next = pred;
            pred = cur;
            cur = succ;
        }
		
		return pred;//pred就是头节点,不用非得返回head,head只是一个名字。pred也可作为名字返回。
        //head->next = cur;//此时cur是空
        //head = pred;
        //delete dummy_node;
        //return head;

    }
};
  • 递归方法(根据双指针流程,确定赋值参数)
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pred = nullptr;
        return reverse(cur,pred);
    }

    ListNode* reverse(ListNode* cur,ListNode* pred){
        if(cur == nullptr)
            return pred;
        //翻转指针
        ListNode* succ = cur->next;
        cur->next = pred;
        return reverse(succ,cur);//一层一层调用reverse,当return pred时,逐层往上return。所以这行是return reverse(succ,cur)
    }
};

遗留问题

网站上第三种解法递归,使链表从后向前翻转,不太明白。等想通之后补充。。。。。

四、总结

很直白的是双指针法,就是记录cur的前一个节点和后一个节点。比对双指针,写出递归。
递归就是重复调用,每次调用不到最后,都要有翻转指针的动作,最后结果不做改变逐层上报。

(欢迎指正,转载表明出处)

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部