JavaScript算法题总结（一）链表

henu_Newxc03

发布于 2022-05-05 18:21:19

2650

发布于 2022-05-05 18:21:19

BM1 反转链表

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead)
{
    // write code here
    //递归终止条件
    if(!pHead||!pHead.next) return pHead;

    let newhead = ReverseList(pHead.next);
    pHead.next.next = pHead;
    pHead.next = null;
    return newhead;
}
module.exports = {
    ReverseList : ReverseList
};

BM2 链表内指定区间反转

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
  */
function reverseBetween( head ,  m ,  n ) {
    // write code here
    //判断条件
    if(!head || !head.next || m===n) return head;
    //找到m前和n后的点start和end
    let start=null,
        end=null,
        cur=head;
    for(let i=1;i<=n;i++){
        if(i===m-1){
            start=cur;
        }
        cur=cur.next;
    }
    end=cur;
    //节点反转
    let pre=null,
        next=null;
    //当不是从头节点开始反转时
    if(m>1){
        cur=start.next;
        while(cur!==end){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        start.next.next=end;
        start.next=pre;
    }else{
        cur=head;
        while(cur!=end){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        head.next=end;
        head=pre;
    }
    return head;
}
module.exports = {
    reverseBetween : reverseBetween
};

BM3 链表中的节点每k个一组翻转

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
  */
function reverseKGroup( head ,  k ) {
    // write code here
    let pre=null;
    let current=head;
    let node=head;
    //判断这一组是否够k个 不够的话直接返回 保持原样
    for(let i=0;i<k;i++){
        if(node===null){
            return head
        }
        node=node.next;
    }
    //反转
    //出来的时候current指向下一组的第一个
    for(let i=0;i<k;i++){
        let next=current.next;
        current.next=pre;
        pre=current;
        current= next;
    }
    // 经过反转后 head已经成为了最后一个节点
    head.next=reverseKGroup(current,k)
    return pre//返回这一组原本的最后一个节点(反转后这个节点已经是第一个节点了)
}
module.exports = {
    reverseKGroup : reverseKGroup
};

BM4 合并两个排序的链表

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2)
{
    // write code here
    if(!pHead1) return pHead2;
    if(!pHead2) return pHead1;
    if(pHead1.val<=pHead2.val){
        pHead1.next=Merge(pHead1.next,pHead2);
        return pHead1;
    }else{
        pHead2.next=Merge(pHead2.next,pHead1);
        return pHead2;
        
    }
}
module.exports = {
    Merge : Merge
};

BM6 判断链表中是否有环

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
function hasCycle( head ) {
    // write code here
    while(head){
        if(head.flag){
            return true;
        }
        head.flag=true;
        head=head.next;
    }
    return false;
}
module.exports = {
    hasCycle : hasCycle
};

BM7 链表中环的入口结点

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function EntryNodeOfLoop(pHead)
{
    // write code here
    //一直往后走 每走一步标记一次 碰到的第一个标记过的就是入口
    while(pHead){
        if(pHead.flag){
            return pHead;
        }else{
            pHead.flag=true;
            pHead=pHead.next;
        }
    }
}
module.exports = {
    EntryNodeOfLoop : EntryNodeOfLoop
};

BM8 链表中倒数最后k个结点

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
function FindKthToTail( pHead ,  k ) {
    // write code here
    if(!pHead||!pHead.next) return 0;
    //快慢指针 先让快指针走k步
    let slow=pHead,fast=pHead;
    for(let i=0;i<k;i++){
        if(!fast) return 0;
        fast=fast.next;
    }
    //再让快慢指针一起走 当快指针到了最末尾 慢指针就到了倒数第k个
    while(fast){
        slow=slow.next;
        fast=fast.next;
    }
    return slow;
}
module.exports = {
    FindKthToTail : FindKthToTail
};

BM9 删除链表的倒数第n个节点

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param n int整型 
  * @return ListNode类
  */
function removeNthFromEnd( head ,  n ) {
    // write code here
    //这个用快慢指针 先让快指针先走n步 然后慢指针与快指针一起走
    //当快指针到了终点的时候 慢指针就到了倒数第n个
    if(head===null) return null;
    let fast=head,slow=head;
    for(let i=0;i<n;i++){
        fast=fast.next;
    }
    //如果fast指针此时为null说明这个n等于链表的长度
    if(fast===null){
        return head.next;
    }
    while(fast.next!==null){
        fast=fast.next;
        slow=slow.next;
    }
    //到这一行的时候slow是倒数第n个节点的前一个节点
    slow.next=slow.next.next;
    return head;
}
module.exports = {
    removeNthFromEnd : removeNthFromEnd
};

BM10 两个链表的第一个公共结点

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
   // write code here
        if (pHead1 == null || pHead2 == null) return null;
    let p1 = pHead1;
    let p2 = pHead2;
    while (p1 !== p2){
        p1 = p1.next;
        p2 = p2.next;
        if (p1 === p2) break;
        if (p1 === null) p1 = pHead2;
        if (p2 === null) p2 = pHead1;
    }
    //这里在外面返回p1是考虑到如果p1 p2第一个节点就是公共的情况
    return p1;
}
module.exports = {
    FindFirstCommonNode : FindFirstCommonNode
};

BM11 链表相加(二)

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head1 ListNode类 
 * @param head2 ListNode类 
 * @return ListNode类
 */
function addInList( head1 ,  head2 ) {
    // write code here
    
    //把所有的节点取出来
    let stack1=[],stack2=[];
    let p1=head1,p2=head2;
    while(p1){
        stack1.push(p1);
        p1=p1.next;
    }
    while(p2){
        stack2.push(p2);
        p2=p2.next;
    }
    
    let jinwei=0;//之前的进位
    let pHead = new ListNode(-1);
    let pre = pHead;
    while(stack1.length||stack2.length){
        let node1=stack1.pop();
        let node2=stack2.pop();
        
        let val1 = node1 ? node1.val : 0;
        let val2 = node2 ? node2.val : 0;
        
        let falseValue=val1+val2+jinwei;
        let trueValue=falseValue%10;
        //进位有可能是0或1
        jinwei = (falseValue - trueValue) / 10;
        let node = new ListNode(trueValue);
        node.next=pre.next;
        pre.next=node;
    }
    if(jinwei===1){
        let node=new ListNode(1);
        node.next=pHead.next;
        pHead.next=node;
    }
    return pHead.next;
}
module.exports = {
    addInList : addInList
};

BM12 单链表的排序

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
function sortInList( head ) {
    // write code here
    let arr=[];
    let p=head;
    while(p){
        arr.push(p.val)
        p=p.next;
    }
    arr.sort((a,b)=>(a-b));//降序排序
    let len=arr.length;
    let node=new ListNode();
    let newHead=node;
    for(let i=0;i<len;i++){
        node.next=new ListNode(arr[i]);
        node=node.next;
    }
    return newHead.next
}
module.exports = {
    sortInList : sortInList
};

BM13 判断一个链表是否为回文结构

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
function isPail( head ) {
    // write code here
    let arr=[],res=[];
    while(head){
        arr.push(head.val);
        res.push(head.val);
        head=head.next;
    }
    arr.reverse();
    for(let i=0;i<arr.length;i++){
        if(arr[i]!==res[i]) return false;
    }
    return true
}
module.exports = {
    isPail : isPail
};

BM14 链表的奇偶重排

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */
function oddEvenList( head ) {
    // write code here
    if(!head||!head.next) return head;
    let arr=[],even=[],odd=[];//even是偶 odd是奇
    while(head){
        arr.push(head.val);
        head=head.next;
    }
    for (let i=0;i<arr.length;i++){
        if(i%2===0) even.push(arr[i]);
        if(i%2===1) odd.push(arr[i]);
    }
    let newHead=new ListNode(null);
    let node=newHead;
    
    for(let i=0;i<even.length;i++){
        node.next=new ListNode(even[i]);
        node=node.next;
    }
    for(let i=0;i<odd.length;i++){
        node.next=new ListNode(odd[i]);
        node=node.next;
    }
    return newHead.next;
}
module.exports = {
    oddEvenList : oddEvenList
};

BM15 删除有序链表中重复的元素-I

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @return ListNode类
  */
function deleteDuplicates( head ) {
    // write code here
    if(!head||!head.next) return head;
    let cur=head;
    while(cur.next){
        if(cur.val===cur.next.val){
            cur.next=cur.next.next;
        }else{
            cur=cur.next;
        }
    }
    return head;
}
module.exports = {
    deleteDuplicates : deleteDuplicates
};

BM16 删除有序链表中重复的元素-II

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @return ListNode类
  */
function deleteDuplicates( head ) {
    // write code here
// write code here
    if(head==null||head.next==null) return head;
    
    let node=new ListNode(0);
    node.next=head;
    
    let pre=node,cur=head;
    
    while(cur!=null&&cur.next!=null){
        if(cur.val===cur.next.val){
            let t=cur.next;
            while(t!=null&&t.val==cur.val){
                t=t.next;
            }
            pre.next=t;
            cur=t;
        }else{
            pre=pre.next;
            cur=cur.next;
        }
    }
    
    return node.next;
}
module.exports = {
    deleteDuplicates : deleteDuplicates
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-05，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

JavaScript算法题总结（一）链表

JavaScript算法题总结（一）链表

BM1 反转链表

BM2 链表内指定区间反转

BM3 链表中的节点每k个一组翻转

BM4 合并两个排序的链表

BM6 判断链表中是否有环

BM7 链表中环的入口结点

BM8 链表中倒数最后k个结点

BM9 删除链表的倒数第n个节点

BM10 两个链表的第一个公共结点

BM11 链表相加(二)

BM12 单链表的排序

BM13 判断一个链表是否为回文结构

BM14 链表的奇偶重排

BM15 删除有序链表中重复的元素-I

BM16 删除有序链表中重复的元素-II

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐