本文由 简悦 SimpRead 转码， 原文地址 mp.weixin.qq.com

常见的链表操作

最近在重新梳理学算法的知识，本文为链表常见操作复习的总结文章，会讲解常见的链表题目实现思路及附上答案，这些题目在 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};

关于奇舞周刊

《奇舞周刊》是 360 公司专业前端团队「奇舞团」运营的前端技术社区。关注公众号后，直接发送链接到后台即可给我们投稿。