算法力扣刷题记录八【206.反转链表】

前言

记录八：力扣【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的前一个节点和后一个节点。比对双指针，写出递归。
递归就是重复调用，每次调用不到最后，都要有翻转指针的动作，最后结果不做改变逐层上报。

（欢迎指正，转载表明出处）