前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构基础之掌握5个常见的链表操作

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

作者头像
winty
发布2020-03-31 17:52:32
2980
发布2020-03-31 17:52:32
举报
文章被收录于专栏:前端Q

常见的链表操作

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

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

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

单链表反转

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

代码语言:javascript
复制
/**
 * @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
};

链表中环的检测

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

代码语言:javascript
复制
/**
 * @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步,当快慢指针相遇时,则有环

代码语言:javascript
复制
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()不能字符串化含有循环引用的结构。

代码语言:javascript
复制
var hasCycle = function(head) {
    try{
        JSON.stringify(head);
        return false;
    }
    catch(err){
        return true;
    }
};

两个有序的链表合并

代码语言:javascript
复制
// 普通方法,遍历合并
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即可。

代码语言:javascript
复制
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步的指针到达链表尾部时,走一步的指针刚好到链表中间

代码语言:javascript
复制
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」,认真学前端,做个专业的技术人...
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-03-25,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 前端Q 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 常见的链表操作
  • 单链表反转
  • 链表中环的检测
  • 两个有序的链表合并
  • 删除链表倒数第 n 个结点
  • 求链表的中间结点
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档