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

骑猪看日落 2023-07-18 14:16 63阅读 0赞

### ![format_png][]    ###

### 常见的链表操作    ###

最近在重新梳理学算法的知识，本文为链表常见操作复习的总结文章，会讲解常见的链表题目实现思路及附上答案，这些题目在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公司专业前端团队「奇舞团」运营的前端技术社区。关注公众号后，直接发送链接到后台即可给我们投稿。

![format_png 1][]

[format_png]: /images/20230528/e27485634efc4bd792e2f0fee79b2875.png
[format_png 1]: /images/20230528/a3779054a3bd4d0494577a714d6cfcb1.png