翻转链表 && 移除链表元素 && 长度最小的子数组

2023/1/3 LeetCode

# 翻转链表

这是力扣 206 题

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

# 解题思路

反转链表大致是如下所示:

image.png

从上图可以清晰地知道,只需要改变链表的 next 指针的指向就可以将链表反转。除此之外,还有一种方法,就是定义一个新的链表,但是这种不是特别推荐,因为需要新的链表,所以会浪费内存空间。至于应该如何改变链表的 next 指针的指向,接下来就来详细介绍一下。

和大部分的链表题目一样,我们可以先把头节点保存下来。首先我们需要定义一个 current 指针,让它指向头节点,再定义一个 pre 指针,并初始化为 null。然后就可以开始反转了。首先要把 current->next 节点用 tmp 指针保存一下,也就是保存一下这个节点。

为什么要保存一下这个节点呢?因为接下来要改变 current->next 的指向了,将 current->next 指向 pre,此时已经反转了第一个节点了。接下来就是循环了,继续移动 precurrent 指针。当 current 指针指向 null 的时候,说明链表反转完毕。最后,只需 return pre 指针就可以了,pre 指针就指向了新的头节点。

这个也可以称为双指针法,因为已经定义好且在不断地移动 precurrent 这两个指针。

相关代码如下:

var reverseList = function(head) {
    let current = head;
    let pre = null;
    let temp = null;
    while(current){
        temp=current.next;
        current.next = pre;
        pre = current;
        current = temp;
    }
    return pre
};

代码非常简短且通俗易懂。并且结合上面的解释一起来看代码也是十分容易理解。相信通过这道题可以强化大家对链表的理解。

# 移除链表元素

这是力扣 203 题

给你一个链表的头节点  head  和一个整数  val ,请你删除链表中所有满足  Node.val == val  的节点,并返回  新的头节点 。

# 解题思路

前面讲了那么多数组相关的题目,现在终于到链表的环节了。这是一道很简单很基础的与链表相关的题目,接下来将会通过这道题来带大家简单地认识一下链表以及链表相关的知识。

什么是链表?链表是一种非连续的存储结构,它由一系列节点构成,链表中的每一个元素称为节点。节点又包括两部分,一是存储此节点数据的数据域,二是存储下一个节点地址的指针域。

那么,数组和链表有什么区别呢?从概念上看,数组在内存中是连续的,链表是不连续的。数组有下标,链表没有下标。数组静态分配内存,链表动态分配内存。

回归到本题上,它让我们移除链表元素,如果是移除数组元素,调用数组的 API 以及加上其他的操作即可,但是链表不一样,它不像数组一样是连续存储的。用大白话来讲,移除链表的某一个元素后,还需将它连接起来。所以,链表有它自己特有的方式来移除元素。

相关代码如下:

var removeElements = function(head, val) {
    const ret = new ListNode(0, head);
    let cur = ret;
    while(cur.next) {
        if(cur.next.val === val) {
            cur.next =  cur.next.next;
            continue;
        }
        cur = cur.next;
    }
    return ret.next;
};

首先设置一个虚拟头节点,将原链表的头节点赋值给虚拟头节点。然后通过 while 循环,当当前节点的值与题目所给的目标值相等时,就将当前节点的下一个节点的值赋给当前节点,并且继续循环。最后 return 返回最终值的时候,是 return ret.next。在链表中区分并理解好指针域和数据域,这题就能很好想清楚了。

# 长度最小的子数组

这是力扣 209 题

给定一个含有  n  个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组  [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

# 解题思路

这道题一眼看过去或许会看不明白,当看了例子之后才理解了。就是找出数组中之和小于 target 且长度最小的一组子数组。碰到数组类型问题,当一时半会没有思路时,二话不说就可以先暴力求解一番。这里用暴力是可以的,不过这道题可以用另一种更好的思路 —— 滑动窗口。接下来就来介绍一下滑动窗口这一解法。

# 滑动窗口

在数组中,还有一个十分重要的操作:滑动窗口。这个方法在数组中被使用到的频率是非常高的,因此掌握滑动窗口至关重要,能解决很多数组问题。什么是滑动窗口,滑动窗口就是通过不断调节起始位置和终止位置,来得到最终的效果。其实如果了解双指针的话,会发现它和双指针有一点点相似,但又不完全像。在某些方面上我会把它当做双指针来理解,毕竟都是需要移动的。

这道题如果使用暴力解法,需要两个 for 循环来完成。若在滑动窗口中,用一个 for 循环即可。使用滑动窗口,需要确定如下三点:

  • 窗口是什么
  • 窗口的起始位置如何移动
  • 窗口的结束位置如何移动

既然是滑动窗口,首先我们要找到窗口。窗口就是满足其和 ≥ s 且长度最小的连续子数组。然后窗口的起始位置如何移动:如果当前窗口的值大于 s 了,窗口就要向前移动了。窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是 for 循环里的索引。

相关代码如下:

var minSubArrayLen = function(target, nums) {
    const len = nums.length;
    let l = r = sum = 0,
        res = len + 1;
    while(r < len) {
        sum += nums[r++];
        // 窗口滑动
        while(sum >= target) {
            res = res < r - l ? res : r - l;
            sum-=nums[l++];
        }
    }
    return res > len ? 0 : res;
};
강남역 4번 출구
Plastic / Fallin` Dild