专栏首页前端Q数据结构基础之掌握5个常见的链表操作

数据结构基础之掌握5个常见的链表操作

常见的链表操作

最近在重新梳理学算法的知识,本文为链表常见操作复习的总结文章,会讲解常见的链表题目实现思路及附上答案,这些题目在leetcode上对应的题号也有给出,好好学习算法吧~

  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第 n 个结点
  • 求链表的中间结点

leetcode 对应题号:206,141,21,19,876

单链表反转

思路:设置2个变量,分别记录其前驱pre和后继next,然后不断 cur.next = pre 就可以了

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head || !head.next) return head

    let cur = head;
    let pre = null;

    while(cur){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre
};

链表中环的检测

思路一:变量标记法,遍历链表且每个遍历项都加上一个唯一标志,若有重复的则链表有环

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let cur = head
  while(cur){
      if(cur.val === 'cycleFlag'){
          return true
      }
      cur.val = 'cycleFlag'
      cur = cur.next
  }
  return false 
};

思路二:快慢指针法,定义快慢2个指针,快的每次走2步,慢的每次走1步,当快慢指针相遇时,则有环

var hasCycle = function(head) {
    if(!head || !head.next)return false
    let slow = head
    let fast = head.next
  while(fast !== slow){
      if(!fast || !fast.next)return false
      fast = fast.next.next
      slow = slow.next
  }
  return true 
};

思路三:奇技淫巧法,利用JSON.stringify()不能字符串化含有循环引用的结构。

var hasCycle = function(head) {
    try{
        JSON.stringify(head);
        return false;
    }
    catch(err){
        return true;
    }
};

两个有序的链表合并

// 普通方法,遍历合并
var mergeTwoLists = function(l1,l2) {
    if(l1 === null)return l2
    if(l2 === null)return l1
    let head = new ListNode(-1)
    let node = head
    while(l1 && l2){
        if(l1.val <= l2.val){
            node.next = l1
            l1 = l1.next
        }else{
            node.next = l2
            l2 = l2.next
        }
        node = node.next
    }
    node.next = l1?l1:l2
    return head.next
};

// 递归合并
var mergeTwoLists = function(l1,l2) {
    if(l1 === null)return l2
    if(l2 === null)return l1

    if(l1.val <= l2.val){
        l1.next = mergeTwoLists(l1.next,l2)
        return l1
    }
    l2.next = mergeTwoLists(l1,l2.next)
    return l2
}

删除链表倒数第 n 个结点

思路:定义2个指针a,b,新建一个空队头,b先走n步,然后a,b再一起走,此时a,b的间隔是n,当b到达队尾时,a刚好在n的前一个节点(因为开始时多建了一个节点),然后让a.next 等于a.next.next即可。

var removeNthFromEnd = function(head, n) {
    if(n === 0) return head
    let p = new ListNode(-1)
    p.next = head
    let a = p
    let b = p
    while(n > 0){
        b = b.next
        n--;
    }

    while(b.next !== null){
        a = a.next
        b = b.next
    }

    a.next = a.next.next
    return p.next
};

求链表的中间结点

思路:2个指针,一个每次走一步,一个每次走2步即可,当走2步的指针到达链表尾部时,走一步的指针刚好到链表中间

var middleNode = function(head) {
    let a = head;
    let b = head;

    while(b != null && b.next != null){
        a = a.next
        b = b.next.next
    }
    return a
};

最后

  • 欢迎加我微信(winty230),拉你进技术群,长期交流学习...
  • 欢迎关注「前端Q」,认真学前端,做个专业的技术人...

本文分享自微信公众号 - 前端Q(luckyWinty),作者:winty

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-03-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 面试必备良药之前端Q本周N题汇总

    最近起了一个新项目,叫每周N题,N<=5。前端面试题虽然五花八门,但是我们也确实可以从中学到知识。所以我觉得应该有个地方收录一下,每周做几题,既可以考验自己知识...

    winty
  • JS实现页面进入、返回定位到具体位置总结

    其实浏览器也自带了返回的功能,也就是说,自带了返回定位的功能。正常的跳转,返回确实可以定位,但是有些特殊场景就不适

    winty
  • 如何1人5天开发完3D数据可视化大屏,超炫酷 【二】

    与地球的实现方法不同,平面地图依赖geojson进行绘制。有什么样的geojson,绘制什么样的地图块。

    winty
  • 链表高频题

    总结:所有链表题目都做过而且都Accept了,不排除有些是抄的。。leet, leet-cn

    王脸小
  • Python 之父的解析器系列之六:给 PEG 语法添加动作

    花下猫语:Guido 的解析器系列更新了 7 篇,他的生产力真旺盛啊。这对于新的解析器来说是件好事,但对于我来说却是个不小的挑战:需要一定的时间和精力,而我对解...

    Python猫
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • 跟我一起学docker(13)--docker Machine的使用

    IT故事会
  • 每日一题-反转链表

    输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

    程序员小王
  • 关于Java两点需要更新的知识

    很多人可以把HashMap的原理描述的很溜。比如JDK1.7之前,底层数据结构是数组+链表。JDK1.8之后,出于效率上的考虑,在数组长度大于64,链表长度大于...

    静儿

扫码关注云+社区

领取腾讯云代金券