分类刷算法题（一）链表

我报名参加金石方案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走到最终的结点
- 删去慢指针的后继节点

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的后继节点，避免回转后丢掉后继链表

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节点
- 堵截
- 部分回转(直接采用上一道题的代码)
- 拼接
这道题直接做或许会容易乱，画个图就好啦~

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 – ()

分类刷算法题（一）链表 | 前端er

一、链表的兼并

二、链表的删去

三、链表回转

四、环形链表

五、链表的相交

六、其他链表题

作者信息

推广

分类刷算法题（一）链表 | 前端er

一、 链表的兼并

二、链表的删去

三、链表回转

四、环形链表

五、链表的相交

六、其他链表题

相关文章

如何用计算器换 MacBook (完)——无心插柳柳成荫

【深入Linux内核架构笔记】第二章 进程调度(3)–完全公平调度CFS

从领英退出中国，解析融云《社交泛娱乐出海作战地图》从0到1出海方法论

面试经典：字符串

作者信息

推广

一、链表的兼并

【深入Linux内核架构笔记】第二章进程调度(3)–完全公平调度CFS