每日一题:反转链表(LeetCode 206)

题目:

给你单链表的头节点head,请你返回反转后的链表。
示例:

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

解答:

链表相关的题目建议在草稿纸上画图理解!
迭代法由于相对好理解,不再记录,以下为递归实现:

/**
 * 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) {
        //当链表为空或结点个数为1时,无需反转(反转前后结果一致),直接返回!
        if(head == NULL || head->next == NULL) return head;

        //递归调用reverseList,第一次return时,head指向倒数第二个结点
        //new head指向尾结点
        ListNode* newHead = reverseList(head->next);

        //第一次执行时,head->next为尾结点
        //第一次执行时,head->next->next为尾结点的指向
        //第一次执行时,以下代码使尾结点指向倒数第二个节点
        head->next->next = head;

        //第一次执行时,清空倒数第二个结点的指向
        head->next = NULL;

        return newHead;

    }
};
THE END
分享
二维码
打赏
海报
每日一题:反转链表(LeetCode 206)
题目: 给你单链表的头节点head,请你返回反转后的链表。 示例: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 解答: 链表相关的题目建议在草稿……
<<上一篇
下一篇>>