• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

JS刷题_链表专题

开发技术 开发技术 4周前 (05-13) 8次浏览

1 从尾到头打印链表

剑指offer_06题

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

输入:head = [1,3,2]
输出:[2,3,1]
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
  const ans = [];
  while(head){
      ans.unshift(head.val);
      head = head.next;
  }
  return ans;

};

2 反转链表

剑指offer_24题

定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路:每次都需要一个中间节点,进行反转

获取 head,和head.next

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    if(!head || !head.next) return head;
    let a = head;
    let b = head.next;
    while(b){
        let c = b.next;
        b.next = a;  //很关键, 不要写反了 , 是修改b.next
        //
        a = b;
        b = c
    }

    head.next = null;
    return a;
};

这个题目,写错过一次,很烦!!!

3 复杂链表的复制

剑指offer_35题

带有next 和 random指针的链表复制,核心:哈希表

/**
 * Definition for singly-linked list with a random pointer.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = this.random = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var copyRandomList = function(head) {
    if(!head) return null;
    let map = new Map();
    map.set(null, null); //很关键。js中如果是null,get是 undefined
    let node = head;
    //复制节点
    while(node){
        map.set(node,new ListNode(node.val));
        node = node.next;
    }
    
    //复制节点的next 和 random
    node = head;
    while(node){
        map.get(node).next = map.get(node.next);  //此时如果node.next 为null,就不需要特判了,set中加好了
        map.get(node).random = map.get(node.random);
        node = node.next;
    }
    
    return map.get(head);
};

4 剑指 Offer 25. 合并两个排序的链表

思路,遍历一遍

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var merge = function(l1, l2) {
    if(!l1) return l2;
    if(!l2) return l1;
    
    //合并两个有序链表,遍历一遍即可
    let dummy = new ListNode(-1);
    let cur = dummy;
    while(l1 && l2){
        if(l1.val < l2.val){
            cur.next = new ListNode(l1.val);
            l1 = l1.next;
            cur = cur.next;
        }else{
            cur.next = new ListNode(l2.val);
            l2 = l2.next;
            cur = cur.next;
        }
    }
    //尾巴
    if(l1) cur.next = l1;
    if(l2) cur.next = l2;
    return dummy.next;
    
};

5 剑指 Offer 22. 链表中倒数第k个节点

思路:注意倒数第k个的含义: 倒数第1个就是 走 n-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) {
    let n = 0;
    let cur = head;
    while(cur){
        n++;
        cur = cur.next;       
    }

    //倒数第k个节点? 倒数第1个节点 从第一个走n-1步
    //倒数第2个    n-2
    cur = head;
    if(k > n) return null;
    for(let i = 0; i < n - k; i ++){
        cur = cur.next;
    }
    return cur;

};

6 142. 环形链表 II

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var entryNodeOfLoop= function(head) {
    if(!head || !head.next) return null;
    let p1 = head.next;
    let p2 = head.next.next;
    //1. 判断是否有环
    while(p1 != p2){
        if(p2 === null || p2.next === null) return null;
        p1 = p1.next;
        p2 = p2.next.next;
    }
    
    //2.相遇 获取环的长度
    let length = 1;
    let tmp = p1;
    p1 = p1.next;
    while(tmp != p1){
        p1 = p1.next;
        length++;
    }
    
    //3.找到公共节点
    p1 = p2 = head;
    for(let i = 0; i < length ; i++){
        p1 = p1.next;
    }
    while(p1 != p2){
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1.val;
    
};

剑指 Offer 52. 两个链表的第一个公共节点

/**
 * 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 p = headA, q = headB;
    while(p != q){
        if(p) p = p.next;
        else p = headB;
        if(q) q = q.next;
        else q = headA;
    }    
    return p;
};

剑指 Offer 62. 圆圈中最后剩下的数字

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var lastRemaining = function(n, m) {
    if( n === 1) return 0;
    else return (lastRemaining(n-1, m) + m) % n;
};

剑指 Offer 18. 删除链表的节点

/**
 * 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) {
    let dummy = new ListNode(-1);
    dummy.next = head;
    let node = dummy;
    while(node.next){
        if(node.next.val === val){
            node.next = node.next.next;
            break;
        }
        node = node.next;
    }
    return dummy.next;
    
};

82. 删除排序链表中的重复元素 II

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let dummy = new ListNode(-1);
    dummy.next = head;

    let p = dummy;
    while(p.next){
        let q = p.next;
        while(q && p.next.val === q.val){
            q = q.next
        }
        //判断长度是否为1
        if(p.next.next == q) p = p.next;
        else p.next = q;
    }
    return dummy.next;
};

程序员灯塔
转载请注明原文链接:JS刷题_链表专题
喜欢 (0)