前端手撕题总结篇（算法篇——来自Leetcode&牛客）

链表

指定区域反转

找到区间（头和为 for循环当**时）->反转链表（返回反转过后的头和尾）->连接

function reverseBetween( head ,  m ,  n ) {

    //preEnd&cur&nextStart  cur.next断开
    if(m===n)return head;

    const vHeadNode=new ListNode(0);
    vHeadNode.next=head;

    let preEnd=null;
    let cur = vHeadNode;
    
    for(let i=0;i<n;i++){
        if(i===m-1)preEnd=cur;
        cur=cur.next;
    }

    let nextStart =cur.next;
    cur.next=null;
    
    const [start,end]=reverseList(preEnd.next);
    preEnd.next=start;
    end.next=nextStart;

    return vHeadNode.next;
}
function reverseList(head){
    const vHeadNode=new ListNode(-1);
    vHeadNode.next=head;
    let cur=head;
    while(cur){
        const next=cur.next;
        cur.next=vHeadNode.next;
        vHeadNode.next=cur;
        cur=next;
    }
    return [vHeadNode.next,head];
}

每K个一组反转（★★★）

指针preEnd&cur->while(cur)->curStart=cur;curEnd=preEnd,if(!preEnd)return vHead.next->反转连接-》cur=nextStart&preEnd=End(翻转过后）

function reverseKGroup(head, k) {
    // write code here
    
    const vHeadNode=new ListNode(-1);
    vHeadNode.next=head;
    let preEnd=vHeadNode;
    let cur=head;
    while(cur){
        let curStart=cur;
        let curEnd=preEnd;
        for(let i=0;i<k;i++){
            curEnd=curEnd.next;
            if(!curEnd)return vHeadNode.next;
        }
        let nextStart=curEnd.next;
        curEnd.next=null;
        const [start,end]=reverseSubList(curStart);
        preEnd.next=start;
        end.next=nextStart;

        cur=nextStart;
        preEnd=end;
    }
    return vHeadNode.next;
}
//反思一下自己吧！！！简单但请仔细
function reverseSubList(head) {
    let dummyNode = new ListNode(0);
    let cur = head;
    while (cur) {
        let next = cur.next;
        cur.next = dummyNode.next;
        dummyNode.next = cur;
        cur = next;
    }
    return [dummyNode.next, head];
}

合并K个已排序链表（★★★）

基础：合并两个已排序链表->归并排序

export function mergeKLists(lists: ListNode[]): ListNode {
    // // write code here
    // //nlogn --->归并
    // //拆开

    // //返回的是ListNode不是数组类型，ts编译会报错！太好了
    
    // if(lists.length<=1) return lists[0];
    // const mid=Math.floor(lists.length/2);
    // const left=mergeKLists(lists.slice(0,mid));
    // const right=mergeKLists(lists.slice(mid));
    // return merge(left,right);

    if(lists.length<=1)return lists[0];
    const mid =Math.floor(lists.length/2);
    const left = mergeKLists(lists.slice(0,mid));
    const right=mergeKLists(lists.slice(mid));
    return merge(left,right);
}

function merge(pHead1:ListNode, pHead2:ListNode) {
    const dummyNode = new ListNode(0);
    let cur = dummyNode;
    while (pHead1 && pHead2) {
        if (pHead1.val < pHead2.val) {
            cur.next = pHead1;
            pHead1 = pHead1.next;
        } else {
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }
        cur = cur.next;
    }
    cur.next=pHead1?pHead1:pHead2;
    return dummyNode.next;
}

基础

//双指针判断是否有环
function hasCycle( head ) {
    if(!head)return false;
    //起点相同
    let fast=head;
    let slow=head;
    //&&这里出错
    while(fast&&slow&&fast.next){
        //先跳后判断
        fast=fast.next.next;
        slow=slow.next;
        if(fast===slow)return true;
    }
    return false;

}
//链表环的入口
function EntryNodeOfLoop(pHead)
{
   if(!pHead||!pHead.next)return null;
   let fast=pHead;
   let slow=pHead;
   while(fast&&slow&&fast.next){
        fast=fast.next.next;
        slow=slow.next;
        if(fast===slow){
            fast=pHead;
            //这！！！
            while(fast!==slow){
                fast=fast.next;
                slow=slow.next;
            }
            return fast;
        }
   }
}
//倒数第	K个节点
function FindKthToTail( pHead ,  k ) {
    // write code here
    //测试案例II,求长度！
    const genLen=(curNode)=>{
        let count=0;
        while(curNode){
            curNode=curNode.next;
            count++;
        }
        return count;
    }
    const len=genLen(pHead);

    //判断是否合理！！！
    if(k>len)return null;

   
    let fast=pHead,slow=pHead;
    while(k--){
        fast=fast.next;
    }
    //这条件！！！
    while(fast){
        fast=fast.next;
        slow=slow.next;
    }
    return slow;
}
//删除链表的倒数第n个节点(虚拟头结点）
function removeNthFromEnd( head ,  n ) {
    // write code here
    let vHeadNode=new ListNode(0);
    vHeadNode.next=head;
    let fast=vHeadNode;
    let slow=vHeadNode;

    while(n--){
        fast=fast.next;
    }
    // //若不借助虚拟节点
    // //这一步真是太关键了
    // if(quick == null){
    //     return head.next
    // }

    //key:此处判断条件就不一样 fast.next&&slow.next！！！
    while(fast.next){
        fast=fast.next;
        slow=slow.next;
    }
    slow.next=slow.next.next;
    return vHeadNode.next;
}
//两链表第一个公共节点
export function FindFirstCommonNode(pHead1: ListNode, pHead2: ListNode): ListNode {
    //另一种思路：求长度差+先走+while相等退出返回
  //循环条件应该是当两个指针没有相遇时继续循环，即while(cur1 !== cur2)。
  //这样，当它们相等时（无论是相交节点还是都为null）就退出循环并返回cur1（此时等于cur2）
    if(!pHead1||!pHead2)return null;
    let cur1=pHead1;
    let cur2=pHead2;
    while(cur1!==cur2){
        cur1=cur1?cur1.next:pHead2;
        cur2=cur2?cur2.next:pHead1;
    }
    return cur2;
}

链表相加（★★★）

先反转+链表相加（大数相加）+反转结果

function addInList( head1 ,  head2 ) {
    // write code here
    const dummyNode=new ListNode(0);
    let cur=dummyNode;
    let reversedList1=reverseList(head1);
    let reversedList2=reverseList(head2);
    let carry=0;

    while(reversedList1||reversedList2||carry){
        let val1=reversedList1?reversedList1.val:0;
        let val2=reversedList2?reversedList2.val:0;
        const sum=val1+val2+carry;
        const digit=sum%10;
        const node =new ListNode(digit);
        carry=Math.floor(sum/10);
        
        cur.next=node;
        cur=cur.next;

        //!!!移动指针！！！链表相加肯定要移动指针!!!
        if(reversedList1)reversedList1=reversedList1.next;
        if(reversedList2)reversedList2=reversedList2.next;


    }
    return reverseList(dummyNode.next);
}
function reverseList(head){
    let vHeadNode=new ListNode(0);
    let cur=head;
    while(cur){
        let next=cur.next;
        cur.next=vHeadNode.next;
        vHeadNode.next=cur;
        cur=next;
    }
    return vHeadNode.next;
}

单链表排序

分治（归并）排序
key：找链表中点（需借助虚拟头结点）->返回条件->合并（两个已排序链表）

function sortInList( head ) {
    // write code here
    //分治
    if(!head||!head.next)return head;
    const middle=findMiddle(head);
    let right=middle.next;
    middle.next=null;
    const leftHead=sortInList(head);
    const rightHead=sortInList(right);
    const merge=(leftHead,rightHead)=>{
        const dummyNode=new ListNode(0);
        let cur=dummyNode;
        let head1=leftHead;
        let head2=rightHead;
        while(head1&&head2){
            if(head1.val>head2.val){
                cur.next=head2;
                head2=head2.next;
            }else{
                cur.next=head1;
                head1=head1.next;
            }
            cur=cur.next;
        }
        cur.next=head1?head1:head2;
        return dummyNode.next;
    }
    return merge(leftHead,rightHead);
}
function findMiddle(head){
    //要虚拟头结点!!!!这一个函数错了，导致整个通过不了！！！
   const dummyNode=new ListNode(0);
   dummyNode.next=head;
   let fast=dummyNode;
   let slow=dummyNode;
   while(fast&&fast.next){
        fast=fast.next.next;
        slow=slow.next;
   }
   return slow;
}

回文链表

找链表中节点（同上）-》反转左侧链表-》比较，若有不对等返回false

export function isPail(head: ListNode): boolean {
    // write code here
    const middle=findMiddle(head);
    let leftHead=head;
    let rightHead=middle.next;
    middle.next=null;
   
    const reverseList=(head:ListNode|null):ListNode=>{
        const dummyNode=new ListNode(0);
        let cur=head;
        while(cur){
            const next=cur.next;
            cur.next=dummyNode.next;
            dummyNode.next=cur;
            cur=next;
        }
        return dummyNode.next;
    }
    let reverseRightHead=reverseList(rightHead);
    while(leftHead&&reverseRightHead){
        if(leftHead.val!==reverseRightHead.val)return false;
        leftHead=leftHead.next;
        reverseRightHead=reverseRightHead.next;
    }
    return true;

}
function findMiddle(head:ListNode):ListNode{
    const dummyNode=new ListNode(0);
    dummyNode.next=head;
    let fast=dummyNode;
    let slow=dummyNode;
    while(fast&&fast.next){
        fast=fast.next.next;
        slow=slow.next;
    }
    return slow;
}

链表奇偶排序

指针：odd、even&evenHead
条件：even&&even.head
返回：head

function oddEvenList( head ) {
    if(!head||!head.next)return head;
    // write code here
    let odd=head;//奇数
    let even=head.next;//偶数
    let evenHead=even;//记录偶节点的头结点
    //终止条件：偶节点&偶节点.next不为空！！！！
    //even&&even.next
    while(even&&even.next){
        odd.next=even.next;
        odd=odd.next;
        even.next=odd.next;
        even=even.next;
    }
    odd.next=evenHead;
    return head;
}

删除重复元素

I->cur=head

function deleteDuplicates( head ) {
    // write code here
    let cur=head;
    //链表靠着时next指针，不要想着还计算长度什么！
    while(cur){
        while(cur.next&&cur.val===cur.next.val){
            cur.next=cur.next.next;
        }
        cur=cur.next;
    }
    return head;
    
}

II(♥）

1. 虚拟头结点
2. 找到if(cur.next.val=cur.next.next.val)并存储至temp，内部while（cur.next&&cur.next.val=temp）删除节点
3. 否则就是cur=cur.next

export function deleteDuplicates(head: ListNode): ListNode {
    // // write code here
    // const vHeadNode=new ListNode(0);
    // vHeadNode.next=head;
    // let cur=vHeadNode;
    // let temp=0;

    // while(cur.next&&cur.next.next){
    //     if(cur.next.val===cur.next.next.val){
    //         temp=cur.next.val;
    //         //相同的节点都跳过
    //         while(cur.next&&cur.next.val===temp){
    //             cur.next=cur.next.next;
    //         }
    //     }else{
    //         //其他节点就向后移
    //         cur=cur.next;
    //     }
    // }
    // return vHeadNode.next;


    const vHeadNode=new ListNode(0);
    vHeadNode.next=head;//虚拟头结点，解决第一个和第二个元素就相同的情况
    let cur=vHeadNode;
    let temp=0;

    while(cur.next&&cur.next.next){
        if(cur.next.val===cur.next.next.val){
            temp=cur.next.val;
            while(cur.next&&cur.next.val===temp){
                cur.next=cur.next.next;
            }
        }else{
            cur=cur.next;
        }
    }
    return vHeadNode.next;
}