我报名参加金石方案1期挑战——瓜分10万奖池,这是我的第1篇文章,点击查看活动概况”

  • 分类刷算法题
  • 之前陆陆续续刷了一些,可是感觉都没有真正掌握起来吧,做的题乱七八糟,所以这次决定好好收拾一下好好过一遍
  • 今日要刷的是链表

一、 链表的兼并

  • 剑指 Offer 25. 兼并两个排序的链表 – 力扣(LeetCode)
  • 主要运用的便是’牵线搭桥’的思路,比较两个,那个比较小就给那个串起来
  • 难度:简略
  • 思路:
    • 初始化dummy伪结点,cur指向dummy结点
    • 进入while循环:当l1为空或许l2为空时跳出循环
      • 当l1.val<l2.val时,cur后继结点指向l1,l1向前走一步
      • 当l1.val<l2.val时,cur后继结点指向l2,l2向前走一步
      • cur向前走一步
    • 兼并剩余的部分
var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode();
    let cur = dummy;
    //两个都节点都存在时,就一向穿梭引线
    while(l1 && l2) {
    //当l1的值比较小的时分,cur的next指向l1,反之指向l2
        if(l1.val< l2.val) {
            cur.next = l1
            l1 = l1.next;
        }else{
            cur.next = l2;
            l2 = l2.next;
        }
        //串起一个结点后,‘针’也要向前走一步
        cur = cur.next;
    }
    //最终剩下的就给它直接一整串串起来
    cur.next = l1 === null? l2:l1;
    return dummy.next
};

二、链表的删去

  • 83. 删去排序链表中的重复元素 – 力扣(LeetCode)
  • 这个很常见也很基础
  • 难度: 简略
  • 思路:
    • cur指向head
    • 进入while循环:当cur指向结点为空或cur的后继结点为空时跳出循环
      • 假如cur指向结点值等于其后继结点的值,则让他的后继结点指向其后继结点的后继结点
      • 不然cur向前走一步
var deleteDuplicates = function(head) {
    let cur = head;
    while(cur != null && cur.next!= null) {
        if(cur.val == cur.next.val) {
            cur.next = cur.next.next
        }else{
            cur = cur.next
        }
    }
    return head
};
  • 82. 删去排序链表中的重复元素 II – 力扣(LeetCode)
  • 难度:中等
  • 这道题便是上一道题的衍生了,这道题需求把重复的悉数删去,那么就或许出现头结点也要删去遇到这种情况咱们就要加他加上dummy伪头结点,才能够next指向真实头结点对他进行删去
  • 思路:
    • 初始化dummy结点:让他的后继节点指向head,一起cur指向dummy
    • 进入while循环:cur的后继节点或cur的后继节点的后继节点为空时跳出循环
      • 当cur的后继节点值等于其后继节点的后继节点值时,遍历其后继节点,对该值节点进行删去
      • 不然的话cur向前走一步
var deleteDuplicates = function(head) {
    //dummy伪头结点
    let dummy = new ListNode();
    dummy.next = head;
    let  cur = dummy;
    while(cur.next && cur.next.next) {
        if(cur.next.val == cur.next.next.val) {
            let val = cur.next.val
            while(cur.next && cur.next.val == val) {
                cur.next = cur.next.next;
            }
        }else{
            cur = cur.next;
        }
    }
    return dummy.next
};
  • 剑指 Offer 18. 删去链表的节点 – 力扣(LeetCode)
  • 难度:简略
  • 如上一道题所述,看到删去节点有或许删去第一个节点咱们或许就要设置伪头结点啦;
  • 一起这道题说的是删去一个节点,也便是说假如头结点是需求删去的节点话,咱们能够采用另一种办法,遇到删去节点为头结点时直接回来head.next就行
  • 以上两种思路跟上述题都差不多就不赘述啦
//设置伪头结点
var deleteNode = function(head, val) {
    let dummy = new ListNode();
    dummy.next = head;
    let cur = dummy;
    while(cur && cur.next) {
        if(cur.next.val == val) {
            cur.next = cur.next.next;
            return dummy.next
        }else{
            cur = cur.next;
        }
    }
};
//遇到头结点需求删去,直接回来head.next
var deleteNode = function(head, val) {
    if(head.val == val) return head.next;
    let cur = head;
    while(cur && cur.next) {
        if(cur.next.val == val) {
            cur.next = cur.next.next;
            return head;
        }else{
            cur = cur.next;
        }
    }
};
  • 剑指 Offer II 021. 删去链表的倒数第 n 个结点 – 力扣(LeetCode)
  • 难度: 中等
  • 这道题咱们采纳新的思路-快慢指针
  • 遇到触及相对杂乱的链表操作,比方回转、指定方位的删去等等常常需求触及到重复遍历,解决这类题,咱们用到的是双指针中的“快慢指针”
  • 快慢指针指的是两个一前一后的指针,两个指针往同一个方向走,只是一个快一个慢
  • 触及链表操作、尤其是触及结点删去的标题,我都主张我们写代码的时分直接把dummy给用起来,建立好的编程习惯,这个在后面也不会再赘述啦
  • 还有一道很类似的题,做完这道题也能够试一试喔:剑指 Offer 22. 链表中倒数第k个节点 – 力扣(LeetCode)
  • 思路:
    • 设置伪头结点
    • 初始化快指针fast, 慢指针low 都指向dummy
    • 先让快指针走K步(意图:当快指针走到最终的结点时,慢结点刚好指向倒数第K个结点的前继结点)
    • 让快慢指针同频向前走直到fast走到最终的结点
    • 删去慢指针的后继节点

分类刷算法题(一)链表 | 前端er

var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode();
    dummy.next = head;
    let fast  = dummy;
    let slow = dummy;
    while(n!=0) {
        fast = fast.next;
        n--
    }
    while(fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next
};

做完上述的题还能够试试以下的题哦

203. 移除链表元素 – 力扣(LeetCode): 这个题跟上述剑指offer18的题很像

三、链表回转

  • 剑指 Offer II 024. 回转链表 – 力扣(LeetCode)
  • 难度: 简略
  • 上述标题咱们用到了双指针法的快慢指针,那咱们这道题用一下多指针法
    • pre,cur,next顺次指向接连结点
    • pre为cur的前继结点,用于回转链表
    • cur为当前结点,通过cur遍历
    • next指向cur的后继节点,避免回转后丢掉后继链表

分类刷算法题(一)链表 | 前端er

var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while(cur) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre
};
  • 92. 回转链表 II – 力扣(LeetCode)
  • 难度:中等
  • 这道题跟上一道题很像,不相同的是上一道题是悉数回转,这道题属于部分回转
  • 采用先回转再拼接,所以记住要把left的前一个节点和right的后一个节点记录下来
  • 思路:
    • 初始化伪头结点dummy
    • 初始化leftNode,rightNode,通过for循环让其别离指向left的前继结点和right节点
    • 堵截
    • 部分回转(直接采用上一道题的代码)
    • 拼接
  • 这道题直接做或许会容易乱,画个图就好啦~
    分类刷算法题(一)链表 | 前端er
var reverseBetween = function(head, left, right) {
    let dummy = new ListNode();
    dummy.next = head;
    let leftNode = dummy;
    let rightNode = dummy;
    //走到left的前继结点
    for(let i =0 ;i<left-1; i++) {
        leftNode = leftNode.next;
    }
    //走到right结点
    for(let i=0; i<right; i++) {
        rightNode = rightNode.next;
    }
    //记录下list1和list2
    let list1 = leftNode.next;
    let list2 = rightNode.next;
    //堵截
    leftNode.next = null;
    rightNode.next  = null;
    //回转中心链表
    let list3 = reverseList(list1);
    //拼接
    leftNode.next = list3;
    list1.next = list2;
   //回来
   return dummy.next
};
var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while(cur) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre
};

四、环形链表

  • 141. 环形链表 – 力扣(LeetCode)
  • 难度: 简略
  • 遇到环形的还能够多加一个判断:假如只有两个结点的话,是无法构成环形的
  • 这道题的办法太多啦而且都是很常见的办法
  • 能够运用哈希表,哈希表存储已经通过的结点,假如通过的节点相同的就阐明环形了
  • 也能够运用上面说过的双指针里边的快慢指针:假如链表是环形的,那么快指针必定会追上慢指针
  • 也能够运用最简略的符号办法:我通过就把它的flag变为true,只有我通过的节点flag为true,那么必定成环了
var hasCycle = function(head) {
    //运用快慢指针
    //假如只有两个节点也构不成环形链表
    if(head == null || head.next == null || head.next.next == null) return false
    let n1 = head;
    let nn = head.next;
    while(n1 != nn){
        //下一个节点能够为空阐明不环形
        if(nn.next == null || nn.next.next == null) {
            return false;
        }
        //一个每次走一步一个每次走两步,构成快慢
        n1 = n1.next;
        nn = nn.next.next;
    }
    return true
};
var hasCycle = function(head) {
    //运用flag
    //假如只有两个节点也构不成环形链表
    if(head == null || head.next == null || head.next.next == null) return false
    while(head) {
        if(head.flag) {
            return true
        }else{
            head.flag = true;
            head = head.next;
        }
    }
    return false
};
  • 142. 环形链表 II – 力扣(LeetCode)
  • 难度:中等
  • 这道题跟上面基本相同啦,改一下回来值就好啦
var detectCycle = function(head) {
    if(head == null || head.next == null || head.next.next == null) return null
    while(head) {
        if(head.flag) {
            return head
        }else{
            head.flag = true;
            head = head.next;
        }
    }
    return null
};

五、链表的相交

  • 160. 相交链表 – 力扣(LeetCode)
  • 难度: 简略
  • 这个题的思路便是假如我相交的话,那么两个指针别离在两个链表走一遍,那么必定会有相交的结点
    • 若两链表 公共尾部 (即 c > 0c>0 ) :指针 A , B 一起指向第一个公共节点node
    • 若两链表 公共尾部 (即 c = 0c=0 ) :指针 A , B 一起指向 null
var getIntersectionNode = function(headA, headB) {
    //假如有一个链表为空的话那么必定不会相交
    if(headA === null || headB === null) return null
    let pA = headA;
    let pB = headB;
    //这儿没有相交是不会死循环哦,因为会一起指向null,也是持平;所以退出循环不必定是没有相交
    while(pA != pB) {
        //假如pA指向的为空,则切换到headB ,不然就指向其后继节点
        pA = pA === null? headB: pA.next;
         //假如pB指向的为空,则切换到headA ,不然就指向其后继节点
        pB = pB === null? headA: pB.next;
    }
    return pA
}; 

六、其他链表题

  • 876. 链表的中心结点 – 力扣(LeetCode)
  • 难度:简略
  • 当快指针走到最终的时分,慢指针刚好在中心结点
var middleNode = function(head) {
    //运用快慢指针
    let fast = head;
    let slow = head;
    while(fast && fast.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow
};

以上代码是自己做题的总结,或许不行完美哈哈哈,主张仍是多看看LeetCode的题解喔

还能够看看其他分类刷题集哦

  • 分类刷算法题(二)栈和队列 | 前端er – ()
  • 分类刷算法题(三)数组操作 | 前端er – ()
  • 分类刷算法题(四) 二分查找 | 前端er – ()
  • 分类刷算法题 (五) 二叉树 | 前端er – ()