反复遍历链表,尝试快慢指针和多指针

简介: 反复遍历链表,尝试快慢指针和多指针

反复遍历链表,尝试快慢指针和多指针


最近在看数据结构和算法,努力总结出道~

TL;DR

  • 链表就是嵌套的对象,{val:1,next:{val:2,next:...}}
  • 链表里的指针,听起来很抽象,其实就是部分链表,依旧是嵌套对象,p 是{val:1,next:{val:2,next:...}}
  • 指针往后挪动,其实就是p = p.next,也就是 p 变成{val:2,next:...}
  • 链表的最后一个节点,next肯定是空的
  • 处理链表的时候,一般为了边界问题,很多时候先创建一个空节点,指向链表,有备无患吧
  • 删除节点必须要知道前置节点
  • 反转链表就是反转指针
  • 反复遍历链表的时候,考虑下快慢指针和多指针

练习:删除倒数第 n 个结点

网络异常,图片无法展示
|

先说说,初始想法:

链表里遍历,只能从前往后,所以删除倒数第 n 个结点,就是删除第len+1-n个,比如总共 5 个结点,删除倒数第 1 个结点,其实就是第 5 个结点,当然链表里删除节点需要知道前置节点,也就是知道倒数第n+1个结点。

于是遍历链表知道链表的长度,然后再遍历链接到第len-n个结点处开始删除第len+1-n个节点,但这样就是嵌套遍历。

怎么能一次遍历就能成功呢?

其实这里,想想双指针法,可以记录遍历的进度。

倒数第n+1个结点距离最后一个节点是n步,换言之,如果有两个指针相隔n步,那么前面的指针到达终点时,后一个指针恰好到了倒数第n+1的结点处,就可以顺手的删掉倒数第n个结点了。

这种两个指针,同个方向,一前一后,就是快慢指针法,解决差距的问题。

  • 处理边界问题,提前创建空节点
  • 快指针先走 n 步
  • 然后快慢指针一起走,直到快指针走到终点,那么慢指针也就到了倒数第n+1个结点处
  • 删除后面一个节点
var removeNthFromEnd = function (list, n) {
  // 处理边界问题,加个空节点
  let head = new ListNode();
  head.next = list;
  // 定义快慢指针
  let slow = head;
  let fast = head;
  // 快指针先走n步
  for (let count = 0; count < n; count++) {
    fast = fast.next;
  }
  // 快慢一起走,直到快指针到终点,慢指针也就到了倒数第n+1个结点处
  while (fast && slow && fast.next && slow.next) {
    fast = fast.next;
    slow = slow.next;
  }
  // 删除倒数第n个结点
  slow.next = slow.next.next ? slow.next.next : null;
  return head.next;
};

可以看下官方题解的其他方案

练习:反转链表

网络异常,图片无法展示
|

处理链表的本质,就是处理指针。

所以反转链表的本质,就是反转指针。

先看下只有两个结点的链表反转:1->2->null

const list = { val: 1, next: { val: 2, next: null } };
// null  1->2
// 建个空节点方便指定
let p0 = null;
let p1 = list;
// 把1后面的链表(这里只有2),先存下,p2就是{val:2,next:null}
let p2 = p1.next;
// 先把1的指针置空,p1就是{val:1,next:null}
// 此时变成 1->null  2
p1.next = p0;
// 再2的指针指向1,p2就是{val:2,next:p1}
p2.next = p1;

三个结点的链表反转:1->2->3->null,其实道理是类似的,但是 p0 和 p1 指针向前移动。

网络异常,图片无法展示
|

var reverseList = function (list) {
  let pre = null;
  let cur = list;
  while (cur) {
    // 必须先保存下一个结点,不然置空cur指针之后,拿不到cur的下一个结点
    let next = cur.next;
    // 反转cur指针
    cur.next = pre;
    // pre和cur指针往前走
    pre = cur;
    cur = next;
  }
  // cur为空的时候,说明pre就是首节点
  return pre;
};

官方视频

练习:反转局部链表

网络异常,图片无法展示
|

这题的第一感觉是和上面的很像,只要先找到要反转的链表区间,然后反转,再重新连接就可以了。

// 官网的注释很明确,直接使用了
var reverseBetween = function (head, left, right) {
  // 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
  const head = new ListNode();
  head.next = head;
  let pre = dummyNode;
  // 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
  // 建议写在 for 循环里,语义清晰
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next;
  }
  // 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
  let rightNode = pre;
  for (let i = 0; i < right - left + 1; i++) {
    rightNode = rightNode.next;
  }
  // 第 3 步:切断出一个子链表(截取链表)
  let leftNode = pre.next;
  let curr = rightNode.next;
  // 注意:切断链接
  pre.next = null;
  rightNode.next = null;
  // 第 4 步:同第 206 题,反转链表的子区间
  reverseLinkedList(leftNode);
  // 第 5 步:接回到原来的链表中
  pre.next = rightNode;
  leftNode.next = curr;
  return dummyNode.next;
};
const reverseLinkedList = (head) => {
  let pre = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
};

时间复杂度是 O(n),空间复杂度是 O(1)。

但是这里遍历了两次列表,想想还能不能继续优化。

新思路:在需要反转的区间里,每遍历到一个节点,让这个新节点来到反转部分的起始位置。

网络异常,图片无法展示
|

根据上面的思路,写出代码

var reverseBetween = function (list, left, right) {
  let head = new ListNode();
  head.next = list;
  let left_pre = head;
  // 将left_pre指针移到在前一个节点处,且以后一直在这个位置
  for (let i = 0; i < left - 1; i++) {
    left_pre = left_pre.next;
  }
  // cur指针也始终不变
  let cur = left_pre.next;
  // 反转right - left次
  for (let i = 0; i < right - left; i++) {
    // next始终是cur的下一个节点
    let next = cur.next;
    // 先修改cur的下一个指针指向
    cur.next = next.next;
    // 然修改next的下一个指针指向
    next.next = left_pre.next;
    // 最后修改left_Pre的下一个指针指向
    left_pre.next = next;
  }
  return head.next;
};

官方题解,这个题解非常细致了

引用

目录
相关文章
|
5月前
|
存储 C语言
用指针处理链表
用指针处理链表
45 3
|
2月前
|
算法 Java
双指针在数组遍历中的应用
文章深入探讨了双指针技术在数组遍历中的应用,通过实战例子详细解释了快慢指针和首尾指针的不同用法,并提供了解决LeetCode相关问题的Java代码实现。
|
3月前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
49 1
【数据结构OJ题】复制带随机指针的链表
|
2月前
|
Python
【Leetcode刷题Python】138. 复制带随机指针的链表
LeetCode上题目“138. 复制带随机指针的链表”的Python解决方案,包括两种方法:一种是在每个节点后复制一个新节点然后再分离出来形成新链表;另一种是构建一个字典来跟踪原始节点与其副本之间的映射关系,从而处理新链表的构建。
15 1
|
2月前
|
存储 算法 数据处理
指针与链表
指针与链表
53 0
|
3月前
|
存储
链表的遍历方式
链表的遍历方式
|
4月前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
26 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
4月前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
5月前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
|
5月前
|
存储 缓存 搜索推荐
指针链表
指针链表
32 0