数据结构基础之掌握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
};