面试算法总结之链表篇 (javascript)

浅浅的花香味﹌ 2022-12-29 15:30 175阅读 0赞

*  链表相关算法总结

--------------------

1、链表的中间节点  
2、相交链表  
3、删除链表的节点  
4、反转链表  
5、反转链表2（[这里是具体的讲解与过程][Link 1]）  
6、链表的倒数第k个节点 （[这里是具体的讲解][Link 2]）  
7、环形链表  
8、回文链表

--------------------

1、链表的中间节点（[跳转到博客][Link 3]）

var middleNode = function(head) { 
        slow = fast = head;
        while (fast && fast.next) { 
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    };

2、相交链表 （[跳转博客][Link 4]）

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */
    var getIntersectionNode = function(headA, headB) { 
        // 清除高度差
        let pA = headA, pB = headB
        while(pA || pB) { 
            if(pA === pB) return pA
            pA = pA === null ? headB : pA.next
            pB = pB === null ? headA : pB.next
        }
        return null
    };

3、删除链表的节点 （[跳转博客][Link 5]）

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @param {number} val * @return {ListNode} */
    var deleteNode = function(head, val) { 
        var prev = new ListNode(-1)
        prev.next = head
        var node = prev
        while(node.next ){ 
            if(node.next.val === val){ 
                node.next = node.next.next
                break
            }
            node  = node.next
        }
        
        return prev.next
    };

4、反转链表

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {ListNode} */
    var reverseList = function(head) { 
        var prev = null,cur=head,temp;
        while(cur){ 
            temp = cur.next;//修改前先记住下一个节点
            cur.next = prev; //改别指向，第一个节点prev是null,
            prev = cur; //记录前一个节点，供下次循环使用
            cur = temp; // cur通过temp指向下一节点
        }
        return prev;//cur会多循环直到null
    };

5、反转部分链表

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} */
    var reverseBetween = function(head, m, n) { 
        if(m===n) return head
        let dummy=new ListNode(0);
        dummy.next=head;
        let d = dummy,a = dummy
        for(let i= 0 ; i < m-1 ; i++) a = a.next
        for(let j = 0 ; j < n ; j++) d = d.next
         let b=a.next ,c=d.next;
        for( p=b,q=p.next;q!==c;){ 
            o = q.next
            q.next = p
            p = q
            q = o
        }
        a.next = d
        b.next = c
    
        return dummy.next
    }

6、删除倒数第k个节点 （[跳转博客][Link 2]）

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @param {number} k * @return {ListNode} */
    var getKthFromEnd = function(head, k) { 
    { 
        var result = [];
        while(head) { 
            result.unshift(head);
            head = head.next
        }
        return result[k-1];
    }}
    
    
    /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @param {number} k * @return {ListNode} */
    var getKthFromEnd = function(head, k) { 
        if(k <=0 || !head || !k ){ 
            return null;
        }
        var fast = head;
        var slow = head;
        for(let i =0 ; i < k-1 ; i++){ 
             if (fast.next) { 
                fast = fast.next
            } else { 
                return null
            }
        }
        while(fast.next){ 
            fast = fast.next;
            slow = slow.next;
        }
        return slow
    
    };

7、环形链表（龟兔赛跑的思路）

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    
    /** * @param {ListNode} head * @return {boolean} */
    var hasCycle = function(head) { 
        if(!head || !head.next){ return false}
        var slow = head
        var fast = head.next
        while(slow!==fast){ 
            if(!fast || !fast.next){ 
            return false
            }
            slow = slow.next
            fast = fast.next.next
        }
        return true
    };

8、回文链表

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */
    /** * @param {ListNode} head * @return {boolean} */
    var isPalindrome = function(head) { 
        var arr=[];
        while(head){ 
            arr.push(head.val);
            head=head.next;
        }
        return arr.toString() === arr.reverse().toString();
    };

[Link 1]: https://blog.csdn.net/qq_39897978/article/details/107177414
[Link 2]: https://blog.csdn.net/qq_39897978/article/details/104746820
[Link 3]: https://blog.csdn.net/qq_39897978/article/details/109387660
[Link 4]: https://blog.csdn.net/qq_39897978/article/details/108638488
[Link 5]: https://blog.csdn.net/qq_39897978/article/details/107244438