常见前端算法题二----链表

1.反转链表

示例：

输入：1->2->3->4->null
输出：4->3->2->1->null

解题思路：将单链表中的每一个节点的后继指针指向它的前驱节点即可。

确定边界条件：当链表为null或链表中仅有一个节点时，不需要反转

var resverList =function(head){
    if(!head || !head.next) return head
    let prev=null
    let current=head
    while(current){
        // 用来临时存储current后继节点
        var next=current.next 
         //反转指针
        current.next=prev  
        // 更新prev,current
        // 待反转节点指向下一个节点
        prev=current  
        current=next  

    }
    head=prev
    return head
}

2.求链表的中间节点

示例：给定一个带有头节点head的非空链表，返回中间节点。

如果有两个中间节点，则返回第二个中间节点

解题思路：快慢指针法，慢指针走一步，快指针走两步，当快指针走到终点时，慢指针刚好指向中间节点

var midleNode =function(head){
    let fast =head
    let slot =head
    while(fast&&fast.next){
        slot=slot.next
        fast=fast.next.next
    }
    return slot
}

3.删除链表倒数第n个节点

解题思路：同样也是快慢指针，只不过快指针提前走n+1步，还得判断一种特殊情况，就是n是不是和链表的长度相等

var removeList=function(head,n){
    let fast=head;
    let slot=head;
    while(--n){
        fast=fast.next; //先走n步
    }
    // 判断链表的长度是不是n,如果刚好走了n步，没有下一个节点，就删除第一个节点并返回
    if(!fast.next)return head.next
    // 如果不是，快指针就再走一步，比慢指针提前走n+1步
    fast=fast.next
    // 快慢指针一起前进
    while(fast&&fast.next){
        fast=fast.next
        slot=slot.next
    }
    slot.next=slot.next.next
    return head

}

4.合并两个有序链表

示例：将两个升序链表合并为一个新的有序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成

解题思路：递归实现

function mergeList(l1,l2){
    if(l1==null)return l2
    if(l2==null)return l1
    if(l1.val<=l2.val){
        l1.next=mergeList(l1.next,l2)
        return l1
    }else{
        l2.next=mergeList(l2.next,l1)
        return l2
    }

}