第七天

力扣第21、102题

21.合并两个有序链表

心得：链表遍历有两种，带头节点的、不带头节点的

//带头节点
while(p.next){
  doSomething(p.next)
  p = p.next
}
//好处就是能访问的上一个节点(父节点)
//不带头节点
while(p){
  doSomething(p)
  p = p.next
}
//不能访问上一个节点(父节点)
//扩展(爷节点)
while(p.next.next){
  doSomething(p.next.next)
  p = p.next
}
//能访问到父、爷节点
//扩展2(遍历两个节点)
while(p1&&p2){
  doSomething(p1)
  doSomething(p2)
  p1 = p1.next
  p2 = p2.next
}
//同时遍历两个链表

实现代码

var mergeTwoLists = function(list1, list2) {
    let preHade = p = new ListNode()
    while(list1&&list2){
        //比较值的大小，小的串上去
        if(list1.val<list2.val){
            p.next = list1;
            list1=list1.next;
        }else{
            p.next = list2;
            list2=list2.next
        }
        p=p.next 
    }
    //上面遍历完了就有一个没了，剩下的一个直接串上去
    p.next = list1||list2; 
    return preHade.next;
      //返回一个不带头节点的链表
};

102.二叉树的层序遍历

bfs 队列

function levelOrder(root) {
    if (!root) return [];
    const res = [];
    const queue = [root];
    while (queue.length) {
        const levelSize = queue.length;
        const level = [];
        for (let i = 0; i < levelSize; i++) {
            const n = queue.shift();
            level.push(n.val);
            n.left && queue.push(n.left);
            n.right && queue.push(n.right);
        }
        res.push(level);
    }
    return res;
};