• leetcode刷题之链表相关问题（js）

    21.合并两个有序链表

    在这里插入图片描述

    var mergeTwoLists = function(list1, list2) {
    if(list1==null) return list2
    if(list2==null) return list1
    let newHead = new ListNode(0,null) //创建一个虚拟节点
    let cur = newHead
    let cur1 = list1,cur2 = list2
    while(cur1&&cur2){
        if(cur1.val<=cur2.val){
            cur.next = cur1
            cur = cur1
            cur1 = cur1.next
        }else{
            cur.next = cur2
            cur = cur2
            cur2 = cur2.next
        }
    }
    while(cur1){
        cur.next = cur1
        cur = cur1
        cur1 = cur1.next
    }
    while(cur2){
        cur.next = cur2
        cur = cur2
        cur2 = cur2.next
    }
    return newHead.next
};

//优化
var mergeTwoLists = function(list1, list2) {
    let cur1 = list1,cur2 = list2
    let newHead = new ListNode(0,null)
    let cur = newHead
    while(cur1&&cur2){
        if(cur1.val<=cur2.val){
            cur.next = cur1
            cur = cur.next
            cur1 = cur1.next
        }else{
            cur.next = cur2
            cur = cur.next
            cur2 = cur2.next
        }
    }
    cur.next = cur1?cur1:cur2
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    23.合并k个有序链表

    在这里插入图片描述
    题解参考

    方法一：纵向比较

    时间复杂度 O(n^2) 空间O(1)

    var mergeKLists = function(lists) {
    //方法一：纵向比较 时间复杂度 O(n^2)  空间O(1)
    //首先去掉lists中的空链表
    for(let i=0;i<lists.length;i++){
        if(!lists[i]){
            lists.splice(i,1)
            //去掉一个成员之后 i-- res：删除一个之后，后面的向前移动了
            i--
        }
    }
    if(lists.length==0) return null
    let newHead = new ListNode(0,null)
    let cur = newHead
    while(lists.length>1){
        let minIndex = 0 //最小的索引
        //接下来比较每个链表的头节点的大小
        for(let j=0;j<lists.length;j++){ //list[i] 就是下标是i的链表的头节点
            if(lists[minIndex].val>lists[j].val){
                minIndex = j
            }
        }
        //连接
        cur.next = lists[minIndex]
        cur = cur.next
        //判断minIndex所在链表的后面是否还是结点
        if(lists[minIndex].next){
            lists[minIndex] = lists[minIndex].next
        }else{
            //当前的链表的所有的结点都已经连接了 那么将该链表从数组中删除
            lists.splice(minIndex,1)
        }
    }
    //while循环结束之后，lists中只剩下一个链表
    while(lists[0]){
        cur.next =lists[0]
        cur = cur.next
        lists[0] = lists[0].next
    }
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    方法二：横向比较

    时间复杂度:O(n^2) 空间复杂度：O(n) 这里要注意：这里我声明了一个新的链表，而不是简单的进行了链表节点指针的改变

    var mergeKLists = function(lists) {
    //横向比较
    //声明两个链表合并的函数
    const merge = (list1,list2) =>{
        if(list1==null) return list2
        if(list2==null) return list1
        //开始进行合并
        let newHead = new ListNode(0,null)
        let cur = newHead
        let cur1 = list1,cur2 = list2
        while(cur1&&cur2){
            if(cur1.val<cur2.val){
                cur.next = cur1
                cur = cur.next
                cur1 = cur1.next
            }else{
                cur.next = cur2
                cur = cur.next
                cur2 = cur2.next
            }
        }
        //连接剩余的
        cur.next = cur1?cur1:cur2
        return newHead.next
    }
    //进行遍历合并
    let temp = null //合并之后的链表
    for(let i=0;i<lists.length;i++){
        temp = merge(temp,lists[i])
    }
    return temp
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    方法三：归并算法

    时间复杂度：O(nlogn) ，res：合并两个链表时间是0(n) 归并排序的次数是O(logn)
    空间复杂度：O(logn),res:递归调用栈使用
    讲解参考

    var mergeKLists = function(lists) {
    //横向比较
    //声明两个链表合并的函数
    const merge = (list1,list2) =>{
        if(list1==null) return list2
        if(list2==null) return list1
        //开始进行合并
        let newHead = new ListNode(0,null)
        let cur = newHead
        let cur1 = list1,cur2 = list2
        while(cur1&&cur2){
            if(cur1.val<cur2.val){
                cur.next = cur1
                cur = cur.next
                cur1 = cur1.next
            }else{
                cur.next = cur2
                cur = cur.next
                cur2 = cur2.next
            }
        }
        //连接剩余的
        cur.next = cur1?cur1:cur2
        return newHead.next
    }
    //进行遍历合并  使用归并算法
    const helper = (lists,start,end) =>{
        //递归跳出
        // if(lists[start]==null) return null //这里是为了解决lists是空的情况 如果lists的第一个链表是空的，但是后面的不是空的 就会出现错误
        if(lists.length==0) return null 
        if(start==end){
            return lists[start]  //划分成了一个链表，那么直接返回
        }
        let mid = start + ((end - start) >>1) //二进制向右侧移动一个位置，相当于除以2
        let left = helper(lists,start,mid)
        let right = helper(lists,mid+1,end)
        return merge(left,right)
    }
    return helper(lists,0,lists.length-1)
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    使用小根堆实现

    参考1
    参考2

    *①时间复杂度 O(nklogk) n链表的长度 k是有几个链表（也即是堆中同时有几个数据） 堆的高度是logk 那么每次调整的时间复杂度是O(logk) 每个链表有nk个结点 记住就行
    ②空间复杂度：O(k) ,res: 堆结构中声明了一个长度为k的数组
    *

    堆的常见操作包括插入、删除最大/最小元素、堆排序等，它们的时间复杂度如下：
    堆的创建：O(n)，其中n为堆中元素的数量。
    插入元素：O(log n)，其中n为堆中元素的数量。
    删除堆顶元素（最大/最小元素）：O(log n)，其中n为堆中元素的数量。
    堆排序：O(n log n)，其中n为堆中元素的数量。
    需要注意的是，这里的时间复杂度都是平均时间复杂度，在最坏情况下，时间复杂度会退化为O(n)。例如，如果在一个最大堆中，需要删除最小元素，则需要将堆中的所有元素都进行调整，时间复杂度会变为O(n)。但是，在实际应用中，由于堆的随机性，该情况出现的概率相对较小

    //定义小根堆 使用数组来保存结构
class minHeap{
    constructor(){ //可以将构造函数看作是类的初始化函数，在创建对象时执行它，相当于其他语言中的构造函数
        this.heap = [] //使用数组来保存堆的相关信息
    }
    //获取小根堆的成员个数
    size(){
        return this.heap.length
    }
    //获取左侧节点的索引
    getLeft(i){
        return 2*i + 1 
    }
    getRight(i){
        return 2*i + 2
    }
    //获取parent节点的索引
    getParent(i){
        return (i-1)>>1
    }
    swap(i1,i2){
        // [list1.val,list2.val] = [list2.val,list1.val]
        // [this.heap[i1].val,this.heap[i2].val] = [this.heap[i2].val,this.heap[i1].val]
        [this.heap[i1],this.heap[i2]] = [this.heap[i2],this.heap[i1]] //注意这里交换的是结点,res:只有交换节点才能保证 出堆的时候能够node.next找到原来的链表的下一个结点
    }
    //向上调整
    shiftUp(index){
        if(index==0) return //如果index是根节点 那么直接返回
        let parentIndex = this.getParent(index)
        if(this.heap[parentIndex]&&this.heap[parentIndex].val>this.heap[index].val){
            this.swap(parentIndex,index)
        }
        //继续向上交换
        this.shiftUp(parentIndex)
    }
    shiftDown(index){
        let left = this.getLeft(index)
        let right = this.getRight(index)
        if(this.heap[left]&&this.heap[left].val<this.heap[index].val){
            this.swap(left,index)
            this.shiftDown(left)
        }
        if(this.heap[right]&&this.heap[right].val<this.heap[index].val){
            this.swap(right,index)
            this.shiftDown(right)
        }
    }
    //向堆中添加成员
    insert(val){
        this.heap.push(val)
        //向上进行调整
        this.shiftUp(this.size()-1)
    }
    //堆顶元素出堆
    getPop(){
        if(this.size()==1) return this.heap.shift()
        //别的情况使用堆的最后一个元素替换
        let top = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.shiftDown(0)
        return top
    }

}

//具体操作
var mergeKLists = function(lists) {
    let newHead = new ListNode(0,null)
    let cur = newHead
    let h = new minHeap()
    //首先链表的头节点入堆
    // for(let i=0;i
    //     if(lists[i]){
    //         h.insert(lists[i])
    //     }
    // }
    lists.forEach(item =>{
        if(item) h.insert(item)
    })
    while(h.size()){
        let top = h.getPop()
        cur.next = top
        cur = cur.next
        if(top.next){
            h.insert(top.next)
        }
    }
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89

    148.排序链表

    在这里插入图片描述

    方法一：使用数组进行排序，然后重新组成新链表

    var sortList = function(head) {
    //方法一：首先将value值保存到数组中，然后进行排序，重新创建链表
    let cur = head
    let arr = []
    while(cur){
        arr.push(cur.val)
        cur = cur.next
    }
    arr.sort((a,b)=>a-b)
    let newHead = new ListNode(0,null)
    cur = newHead
    for(let i=0;i<arr.length;i++){
        cur.next = new ListNode(arr[i])
        cur = cur.next
    }
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    方法二：归并 同23的归并思路

    参考

    var sortList = function(head) {
    //使用归并排序
    //合并链表  时间复杂度：每次合并是O(n) 递归是O(logn) =>O(nlogn) 空间复杂度O(logn) 主要是递归栈
    const merge = (head1,head2) =>{
        //递归跳出
        if(head1==null) return head2
        if(head2==null) return head1
        let newHead = new ListNode(0,null)
        let cur = newHead
        let cur1 = head1,cur2 = head2
        while(cur1&&cur2){
            if(cur1.val<cur2.val){
                cur.next = cur1
                cur = cur.next
                cur1 = cur1.next
            }else{
                cur.next = cur2
                cur = cur.next
                cur2 = cur2.next
            }
        }
        cur.next = cur1?cur1:cur2
        return newHead.next
    }
    //进行归并 start是左侧链表的起始 end是右侧链表的起始
    const helper = (start,end) =>{
        if(start==null) return start  //这种情况是用来对付链表为空的
        if(start.next==end){
            //前后两个链表是不相关的 断开链子 分别返回
            start.next = null
            return start
        }  //进行划分过程中 划分成了一个 那么直接返回
        //使用快慢指针寻找中间结点
        let slow = start,fast = start
        while(fast!==end&&fast.next!==end){ //自己可以数手指头 当链表的个数是奇数个 那么最后slow指向最中间 如果链表的个数是偶数个 那么最后slow指向中间两个节点的后一个 反正这里不用管位置到底那样 只需要找一个位置将这个链表划分成两个即可
            slow = slow.next
            fast  = fast.next.next
        }
        let mid = slow
        return merge(helper(start,mid),helper(mid,end)) //对中点的左右两部分继续递归，然后对递归的返回值进行合并
    }

    return helper(head,null) //最开始只有一条链表 
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    203.移除链表元素

    在这里插入图片描述

    方法一：新建虚拟节点+pre

    var removeElements = function(head, val) {
    if(head==null) return head
    let newHead = new ListNode(0,null)
    let cur = head,pre = newHead
    while(cur){
        if(cur.val==val){
            cur = cur.next
            pre.next = cur//加上这一句才能保证pre会随着cur指针进行筛选
        }else{
            pre.next = cur
            pre = pre.next
            cur = cur.next
        }
    }
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    方法二：参考大佬的写法

    var removeElements = function(head, val) {
    //设置一个虚拟头节点
    let newHead = new ListNode(0,head)
    let cur = newHead
    while(cur.next){
        if(cur.next.val==val){
            cur.next = cur.next.next
            continue
        }
        cur = cur.next
    }
    return newHead.next
};


var removeElements = function(head, val) {
    let newHead = new ListNode(0,head)
    let cur = newHead
    while(cur.next){
        if(cur.next.val==val){
            cur.next = cur.next.next
        }else{
            cur = cur.next
        }
    }
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    707.设计链表

    //定义listnode
class ListNode{
    constructor(val,next){
        this.val = val
        this.next = next
    }
}
//初始化
var MyLinkedList = function() {
    this.head = null
    this.tail = null
    this.size = 0
};
//根据索引值找到节点的位置
MyLinkedList.prototype.getNode = function(index){
    //没有该索引
    if(index<0||index>=this.size) return null
    //遍历找到节点
    let cur = new ListNode(0,this.head)
    while(index-- >=0){ //这里也是一个错误  注意判断次序
        cur = cur.next
    }
    return cur
}

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    if(index<0||index>=this.size) return -1
    return this.getNode(index).val  //注意这里返回val
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    let newHead = new ListNode(val,this.head)
    this.head = newHead
    if(this.tail==null){
        this.tail = this.head
    }
    this.size++             //注意size自增
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    let node = new ListNode(val)
    this.size++
    if(this.tail){      //错误判断，不能直接this.tail = node
        this.tail.next = node
        this.tail = node
        return
    }
    this.head = node
    this.tail = node
    
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    //判断是否是在头添加结点
    if(index<=0){
        this.addAtHead(val)
        return
    }
    if(index>this.size) return
    if(index==this.size){    //这里判断出错，当index==this.size的时候才是在尾部插入
        this.addAtTail(val)
        return
    }
    //在其他位置添加结点
    let preNode = this.getNode(index - 1)
    let newNode = new ListNode(val,preNode.next)
    preNode.next = newNode
    this.size++
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index<0||index>=this.size) return	//当this.size==0的时候一定会跳出 
    if(index==0){
        this.head = this.head.next
        this.size--
        return
    }
    let preNode = this.getNode(index - 1)
    preNode.next = preNode.next.next
    //判断删除的是否是尾部结点           这里有是一个错误
    if(index==this.size-1){
        this.tail = preNode
    }
    this.size--
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116

    206.反转链表

    在这里插入图片描述

    方法一：头插法

    var reverseList = function(head) {
    //头插法
    if(head==null||head.next==null) return head
    //创建一个虚拟节点
    let newHead = new ListNode(-1,null)
    let cur = head
    let nextNode = null
    while(cur){
        //保留cur的下一个节点
        nextNode = cur.next
        cur.next  = newHead.next
        newHead.next = cur
        //然后找回nextNode
        cur = nextNode
    }
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    递归法一

    var reverseList = function(head) {
//这个递归式从后往前进行翻转
    const helper = curNode =>{
        //递归跳出的条件 要考虑空链表的情况所以要加上curNode==null这一判断条件
        if(curNode==null||curNode.next==null) return curNode
        //p相当于是最后一个结点
        let p = helper(curNode.next)
        // if(p!==null){   这里的if语句可以去掉了 只要链表不是空的 那么curNode.next都可以条粗递归
            curNode.next.next = curNode
            curNode.next = null
        // }
        return p
    }
    return helper(head)
};

var reverseList = function(head) {
    //递归法
    let newHead = null
    const helper = node =>{
        if(node==null||node.next==null){
            newHead = node
            return node
        }
        let nextNode = helper(node.next)
        nextNode.next = node
        node.next = null
        return node
    }
    helper(head)
    return newHead
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    递归法二

    var reverseList = function(head) {
    //这种方法是从第一个结点开始向前翻转，一直到最后一个结点
    const helper = (pre,head) =>{
        //递归跳出的条件
        if(head==null) return pre
        let temp = head.next
        head.next = pre
        pre = head
        //向后进行遍历
        return helper(pre,temp)    //整个递归的最后返回值是pre 也就是原链表的最后一个结点
    }
    return helper(null,head)
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    使用栈来进行翻转

    var reverseList = function(head) {
    //使用栈 将所有的结点全都压入栈中 然后创建一个虚拟结点 然后栈中的结点出栈
    if(head==null||head.next==null) return head
    let stack = []
    let cur = head
    //全部入栈
    while(cur){
        stack.push(cur)
        cur = cur.next
    }
    let newNode = new ListNode(0,null)
    let curNode = newNode
    while(stack.length){
        let node = stack.pop()
        curNode.next = node
        curNode = node
    }
    curNode.next = null//防止最后形成一个圈
    return newNode.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    234.回文链表

    在这里插入图片描述

    方法一：使用数组比对

    var isPalindrome = function(head) {
    //方法一：放入到数组中 判断数组是否是回文数组
    let cur = head
    let arr = []
    while(cur){
        arr.push(cur.val)
        cur = cur.next
    }
    //从数组的两头进行比较
    let start = 0,end = arr.length - 1
    while(start<end){
        if(arr[start]!==arr[end]){
            return false
        }
        start++
        end--
    }
    return true
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    方法二：分割链表，然后比对

    var isPalindrome = function(head) {
    //思路：使用快慢指针找到中间节点，将后一段结点进行翻转 然后从头开始进行比对
    if(head==null||head.next==null) return true
    let slow = head,fast = head
    let pre = null
    while(fast&&fast.next){ //如果只有一个结点，那么while循环结束之后，slow fast指向head；如果有两个结点 那么最后slow fast都会指向中间两个结点的后一个结点；总之，当链表的个数是奇数，那么最后slow指向中间结点，如果链表的个数是偶数个，那么最后slow指向中间两个结点的后一个。
        pre = slow
        slow = slow.next
        fast = fast.next.next
    }
    pre.next = null//将前后两段进行分开
    let tempNode = null
    let cur  = slow
    while(cur){
        let nextNode = cur.next
        cur.next = tempNode
        tempNode = cur
        cur = nextNode
    }
    let head2 = tempNode
    while(head&&head2){ //当链表的个数是奇数的时候，中间节点会分在后一段链表中 只要把两段链表的相应部分进行比对完成即可 中间结点不用比对
        if(head.val!==head2.val){
            return false
        }
        head = head.next
        head2 = head2.next
    }
    return true
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    24.两两交换链表中的结点

    在这里插入图片描述

    使用队列进行交换

    var swapPairs = function(head) {
    //使用队列完成
    if(head==null||head.next==null) return head
    let queue = []
    let newHead = new ListNode(0,null)
    let cur = newHead
    //将全部的结点放入队列
    while(head){
        queue.push(head)
        head = head.next
    }
    while(queue.length>=2){  //不满足当前的条件的时候，queue中可能剩余1个或者0个
        let node1 = queue.shift()
        let node2 = queue.shift()
        cur.next = node2
        cur = cur.next
        cur.next = node1
        cur = cur.next
    }
    if(queue.length){    //这里判断是否还有剩余
        let lastNode = queue.shift()
        cur.next = lastNode
        cur = cur.next
    }
    cur.next = null //消除圈
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    原地进行交换

    var swapPairs = function(head) {
    //原地进行交换
    if(head==null||head.next==null) return head
    //进行交换
    let newHead = new ListNode(0,head) //创建一个虚拟节点
    let curNode = newHead.next
    let pre = newHead
    while(curNode&&curNode.next){
        let nextNode = curNode.next.next //保存结点
        pre.next = curNode.next
        pre = curNode
        curNode.next.next = curNode
        curNode.next = nextNode
        curNode = nextNode
    }
    //最后只剩下一个结点 就不用进行交换了
    return newHead.next
};

//修改 ingingingingingingingingigninginginginginginging
var swapPairs = function(head) {
    if(head==null||head.next==null) return head
    //原地进行交换
    let newHead = new ListNode(0,head)
    let cur = newHead
    let nextNode = null
    //cur的下一个结点 cur的下一个的下一个结点
    let firstNode = cur.next,secondNode = cur.next.next
    while(firstNode&&secondNode){
        nextNode = secondNode.next
        secondNode.next = firstNode
        firstNode.next = nextNode
        cur.next = secondNode
        cur = firstNode
        if(cur.next&&cur.next.next){
            firstNode = cur.next
            secondNode = cur.next.next
            continue
        }else{
            break
        }
    }
    return newHead.next
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    递归实现

    参考

    var swapPairs = function(head) {
    //使用递归
    const helper = head =>{
        if(head==null||head.next==null) return head
        let nextNode = head.next //上面的判断语句没有执行，也即是说nextNode!==null
        head.next = helper(nextNode.next)//可以理解为head在承接后面已经处理好的链表
        nextNode.next = head  //nextNode 放到原先的head的前面
        return nextNode
    }
    return helper(head)
};
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    19.删除链表的倒数第n个结点

    在这里插入图片描述

    方法一：使用两次循环找到第n个节点的位置

    var removeNthFromEnd = function(head, n) {
    //方法一:从头开始进行遍历找到第n个结点
    if(head==null) return head
    let sum = 1 //统计链表的总长度
    let cur = head
    while(cur.next){
        sum++
        cur = cur.next
    }
    //如果链表的长度不够
    if(n>sum) return head
    if(n==sum){
         return head.next
    }
    //也即是删除第 sum-n+1个结点  需要找它前面的结点
    let i = 1
    cur = head
    while(i<sum-n){
        i++
        cur = cur.next
    }
    cur.next = cur.next.next
    return head
};

//第二次写 一次有一次的理解
var removeNthFromEnd = function(head, n) {
    //使用两次循环 第一次先找到链表的长度 第二次循环 找到相应的位置
    if(head==null) return head
    let len = 0
    let cur = head
    while(cur){
        len++
        cur = cur.next
    }
    if(n>len) return null
    if(n==len) return head.next
    let needIndex = len - n + 1//比如len = 5 n = 3 那么len - n = 2 也就是要删除第三个结点
    cur = head
    let num = 1
    let pre = null
    while(num!==needIndex){
        num++
        pre = cur
        cur = cur.next
    }
    //最后cur就是要删除的结点
    pre.next = cur.next
    return head
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    方法二：使用快慢指针

    var removeNthFromEnd = function(head, n) {
    //使用快慢指针 当fast指针走了n个位置之后 slow指针开始走动 当fast走到空的时候 slow所指的位置就是倒数第n个位置
    if(head==null) return head
    let slow = head, fast = head
    let i = 1 //记录位置
    //首先fast指针要移动到第n+1个位置
    while(fast.next&&i<=n){
        i++
        fast = fast.next
    }
    if(i<n) return head //也就是说链表的长度小于n
    if(i==n) return head.next//链表的长度正好是n
    //链表的长度够了 那么slow fast同时向前移动
    while(fast.next){
        fast = fast.next
        pre = slow
        slow = slow.next  //slow正好是要删除的位置的前面
    }
    slow.next = slow.next.next
    return head
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    面试题02.07.链表相交

    在这里插入图片描述

    方法一：暴力

    var getIntersectionNode = function(headA, headB) {
    if(headA==null||headB==null) return null
    //首先找出两个链表的长度
    let cur = headA
    let sumA = 1,sumB = 1
    while(cur.next){
        sumA++
        cur = cur.next
    }
    cur = headB
    while(cur.next){
        sumB++
        cur = cur.next
    }
    // console.log(sumA,sumB)
    let len = Math.abs(sumA - sumB)
    // console.log(len,'changdu ')
    if(sumA>sumB){
        //A链表先去移动len个位置
        while(len-- >0){
            headA = headA.next
        }
    }
    if(sumA<sumB){
        while(len-- >0){
            headB = headB.next
        }
    }
    // console.log(headA,headB,'jiedian')
    //移动完成之后 a b 后面的长度相同
    while(headA){
        if(headA==headB) return headA
        headA = headA.next
        headB = headB.next
    }
    return null
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    方法二：根据a+b = b + a

    var getIntersectionNode = function(headA, headB) {
    let A = headA
    let B = headB
    while(A !== B){
        A = A !== null ? A.next : headB
        B = B !== null ? B.next : headA
    }
    console.log(null==null)//true
    return A
};


var getIntersectionNode = function(headA, headB) {
    if(headA==null||headB==null) return null
    //方法二 根据 a+b = b+a 的原理
    let cur1 = headA, cur2 = headB
    while(cur1||cur2){
        if(cur1==cur2) return cur1
        cur1==null?cur1=headB:cur1=cur1.next
        cur2==null?cur2=headA:cur2=cur2.next
    }
    return null
};


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    141.环形链表

    在这里插入图片描述

    使用快慢指针

    var hasCycle = function(head) {
    //使用快慢指针 slow每次走一个位置 fast每次走两个位置 如果链表中有圈 那么fast一定会转一圈然后赶上slow，可以这么理解，slow相对于的fast的位置是不变的，fast相对于slow每次走一个位置，这样如果链表中有圈，那么fast一定可以回到原来的位置
    if(head==null||head.next==null) return false
    let slow = head,fast = head
    while(fast.next){
        fast = fast.next
        if(fast.next){
            fast = fast.next
        }
        slow = slow.next
        // if(slow==fast){ //这样会出现错误 由于上面 进行while循环的时候，fast可以只走一个位置，而此时slow也走一个位置 这样即使是一条链 也会相等
        //     return true
        // }
        if(fast.next==slow){
            return true
        }
    }
    return false
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    快慢指针修改

    var hasCycle = function(head) {
    //使用快慢指针 slow每次走一个位置 fast每次走两个位置 如果链表中有圈 那么fast一定会转一圈然后赶上slow，可以这么理解，slow相对于的fast的位置是不变的，fast相对于slow每次走一个位置，这样如果链表中有圈，那么fast一定可以回到原来的位置
    if(head==null||head.next==null) return false
    let slow = head,fast = head
    while(fast&&fast.next){
        fast = fast.next.next
        slow = slow.next
        if(slow==fast){//如果有圈的话，那么fast slow会在圈中相遇 如果没有圈，那么fast会提前为空，然后跳出while循环
            return true
        }
    }
    return false
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    142.环形链表2

    在这里插入图片描述

    方法一：使用map保存节点信息

    var detectCycle = function(head) {
    if(head==null||head.next==null) return null
    //使用map对象来保存遍历过的结点
    let map = new Map()
    let cur = head
    while(cur.next){
        if(map.has(cur)){
            //如果map中有这个结点 那么这个结点就是圈的起点
            return cur
        }else{
            map.set(cur,1)
        }
        cur = cur.next
    }
    return null
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    方法二：快慢指针

    在这里插入图片描述
    思路：
    ①当slow指针和fast指针相遇的时候,slow走了x+y;fast走了x+y+n(y+z);
    ②由于fast的速度是slow的2倍，所以有2(x+y)=x+y=n(y+z)
    ③移项得x = n (y + z) - y
    ④令n=1得到x=z,也即是当slow和fast第一次相遇的时候，如果这时候有一个结点temp从head出发，那么temp和slow同时移动，当temp==slow的时候，temp就是入口结点
    参考代码随想录

    var detectCycle = function(head) {
    if(head==null||head.next==null) return null
    let slow = head,fast = head
    while(fast&&fast.next){
        fast = fast.next.next
        slow = slow.next
        if(slow==fast){
            //既然是有环的 那么就要去找这个环的入口
            fast = head
            while(fast!==slow){
                fast = fast.next
                slow = slow.next
            }
            return fast
        }
    }
    return null //没有圈
};



var detectCycle = function(head) {
    //快慢指针 fast每次走两个位置 slow每次走一个位置
    // a + 2b + c = 2(a + b) => c = a 当fast指针进入环之后，slow还未进入环，假设fast slow同时入环，那么当fast走了一圈之后，slow走了半圈，可是fast比slow先入环，那么当fast与slow相遇的时候，slow在环内正在第一圈。这里我们假设从入环结点到fast slow相遇的结点之间的距离是b，head到入环结点之间的距离是a，c是二者相遇的结点到入口结点之间的距离，当二者相遇的时候，令fast = head，那么二者再次相遇时候，即是入口
    if(head==null||head.next==null) return null
    let slow = head,fast = head
    while(fast&&fast.next){
        slow = slow.next
        fast = fast.next.next
        if(slow==fast) break
    }
    if(fast==null||fast.next==null) return null //这种情况说明没有环
    fast = head
    while(fast!==slow){
        fast = fast.next
        slow = slow.next
    }
    return slow
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39

    146.LRU缓存

    在这里插入图片描述
    思路：使用map对象，因为map对象的成员是有先后循序的，每次get的时候，先判断原来的map中是否有这个成员，如果有的话，将其先删除再将其set，这样这个刚刚访问过的成员就被重新放入到了map的最后一个，经过这样一直的操作，最后map的第一个成员就是根据LRU算法的要求，要出去的。
    参考教程
    map使用了iterator的相关信息，参考

    /**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    //使用map对象 map对象中的每个键是有先后顺序的，
    this.map = new Map() //this指向LRUCache
    this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.map.has(key)){
        let value = this.map.get(key)
        this.map.delete(key)  //删除之后再去set 相当于将其放到了最后一位
        this.map.set(key,value)
        return value
    }else{
        return -1
    }
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    //为了实现LRU 最近最少使用的要求 每次访问一个元素之后，先将其删除，让后再添加到map中，这样就是加入到map对象的末尾，一直这样操作，map对象的第一个key就是最近最少使用的
    if(this.map.has(key)){
        this.map.delete(key)
        this.map.set(key,value)
    }else{
        //这里是先将key value加入到map中然后判断map中的成员数量，如果超了 那么就删除第一个成员
        this.map.set(key,value)
        if(this.map.size>this.capacity){
            //map对象是可迭代的 keys()返回一个新的迭代对象 next()是迭代器中的函数 它可以获取map的迭代对象的第一个成员 如果再去next 那么获取第二个成员
            this.map.delete(this.map.keys().next().value)
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
  • 相关阅读:
    FreeMarker快速入门详解
    【C++】string类模拟实现上篇(附完整源码）
    8万字带你入门Rust
    如何设定员工满意度调研的维度？
    四十、手搭简易Web框架
    【JavaEE重点知识归纳】第5节：方法
    毕业从事弱电3个月，我为什么会选择转行网络工程师
    无序链表的归并排序 - Java代码纯享版
    工业镜头的景深、分辨率及如何匹配合适的工业相机-51camera
    在 android 上使用 adb client
  • 原文地址：https://blog.csdn.net/qq_43667537/article/details/130860843