代码编织梦想

力扣 206. 反转链表

题目

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

示例 1:

img

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

示例 2:

img

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

示例 3:

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

提示:

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

两种解法

  • 迭代
  • 递归

我不避讳,在我最初拿到这道题,是尝试以递归思路做的,但是独自操作之下,把指针和结点搞迷糊了,算是解不出来了,惭愧惭愧

迭代

迭代的话,我个人感觉相较于递归更难理解,但是实现出来的方法思想更加精妙

这道题递归给我的感觉就像是交换雪碧和可乐的杯子的样子

我也不知道会有这样的感觉

  • 时间复杂度 O(n)

  • 空间复杂度 O(1)

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 迭代
    let pre = null;
    let cur = head;
    while(cur) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};

递归

递归,我理解的话就是,将问题转化为该问题更小一步规模的过程,当题目符合这样的思想就有可操作性了,注意写一下边界条件,这个边界条件,往往就是该问题在最小规模下的解法

水平有限,大概只能这么解释了

  • 时间复杂度 O(n)

  • 空间复杂度 O(n) 递归的空间复杂度主要递归调用的栈空间

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // 递归
    if(head == null || head.next == null) {
        return head;
    }
    let p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
};

能力有限,仅供参考

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_51126511/article/details/128012196

力扣 206. 反转链表-爱代码爱编程

反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 借鉴力扣题解区 路漫漫我不畏dalao的思路: 定义两个指针:pre在前,cur在后 每次进行局部反转,然后pre和cur共同前进一个位置,直到pre指向null

力扣206.反转链表(java)-爱代码爱编程

力扣206.反转链表 题目思路代码 LeetCode笔记汇总 题目 思路 双指针迭代 迭代的思想是从左边开始两两交换链表中的节点。交换两个节点,使用一个长度为3的滑动窗口。窗口中的元素分别为pre,cur,temp。实际交换的是前两个节点,第三个temp节点主要用于存储,避免在改变cur.next后访问不到原链表中cur后面的元素。最开

力扣206. 反转链表-爱代码爱编程

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 方法一:双指针 一次遍历链表,遍历到的每一个节点,让当前节点的下一个节点指向它的上一个节点 class Solution { public: ListNode* reverseList(ListNode* head) { //当head为空,或只含有h

力扣 206.反转链表-爱代码爱编程

问题描述 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例1:  输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 示例2:   输入:head = [1,2] 输出:[2,1]  示例3: 输入:head = [] 输出:[]  解题思路 /**

LeetCode206.反转链表(C++)-爱代码爱编程

 题目见https://leetcode-cn.com/problems/reverse-linked-list/ // 解法1:用三个指针来实现 // class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* pre = NULL;

力扣206.反转链表(Python版本)-爱代码爱编程

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 思路:如果不断向一个链表首端插入结点,最早放进去的结点将在表的最后(即尾结点),而从表的首端取下结点,最后取下的是尾结点。也就是说,从一个表的首端不断取下结点,将其加入到另一个结点的首端,就形成了一个反转的过程。取下和加入的操作都是O(1)的,总的时间开销是O(n),所以这是一个高

力扣算法js lc [203. 移除链表元素] lc [206. 反转链表]_想学好前端的小宝的博客-爱代码爱编程

LC 203. 移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出

力扣92. 反转链表 ii_isabelle_yan的博客-爱代码爱编程

力扣 92. 反转链表 II 链接 思路 把需要转置的部分放到数组里,转置之后再放回原链表 代码 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val

力扣206.反转链表_九叔的博客-爱代码爱编程

1、题意:   本题是对链表进行操作,实际是对链表的节点的操作。 2、思路: 直接暴力过,将本元素的next指向上一个元素(第一个元素指向null)。z用于储存y指针的下一跳(原链表),x存储原链表的上一跳,y用于遍历节点。  3、代码实现: /** * Definition for singly-linked list. * publi

力扣206.反转链表(java解法)_psvm_code的博客-爱代码爱编程

题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。  这题反复做过好多次,这次将自己的思路总结后记录下来。 思路一:(双指针) 用双指针改变原链表中的指针的指向即可。初始化一个指针cur指向头结点head,初始化一个指针pre指向空。 ListNode cur = head; ListNode pre = null; 其

力扣 206.反转链表-爱代码爱编程

题目描述 给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 示例1: 输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1] 示例二: 输入:head =