大厂算法面试之 leetcode 精讲 15. 链表

var reverseList = function (head) {  let temp = new ListNode();  let next = null;  while (head) {    next = head.next;//下一个节点    head.next = temp.next;    temp.next = head;//head接在temp的后面    head = next;//head向后移动一位  }  return temp.next;};

var reverseList = function (head) {  let prev = null;  let curr = head;  let next = null;  while (curr !== null) {    next = curr.next;//next向后移动一位    curr.next = prev;//让当前指针curr.next指向前一个指针prev    prev = curr;//prev向后移动一位    curr = next;//curr向后移动一位    //[curr.next, prev, curr] = [prev, curr, curr.next]  }  return prev;};

class Solution {    public ListNode reverseList(ListNode head) {        ListNode prev = null;        ListNode curr = head;        while (curr != null) {            ListNode next = curr.next;            curr.next = prev;            prev = curr;            curr = next;        }        return prev;    }}

var reverseList = function(head) {    if (head == null || head.next == null) {//递归终止条件        return head;    }    const newHead = reverseList(head.next);//递归调用reverseList    head.next.next = head;//到了递归最后一层的时候，让后面一个节点指向前一个节点    head.next = null;//前一个节点的next置为空    return newHead;//返回最后一个节点};

class Solution {    public ListNode reverseList(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode newHead = reverseList(head.next);        head.next.next = head;        head.next = null;        return newHead;    }}

var reverseBetween = function(head, left, right) {    const dummyNode = new ListNode(-1);    dummyNode.next = head;//虚拟头节点
    let pre = dummyNode;    for (let i = 0; i < left - 1; i++) {//pre遍历到left的前一个节点        pre = pre.next;    }
    let rightNode = pre;    for (let i = 0; i < right - left + 1; i++) {//rightNode遍历到right的位置        rightNode = rightNode.next;    }
    let leftNode = pre.next;//保存leftNode    let curr = rightNode.next;//保存rightNode.next
    //切断left到right的子链    pre.next = null;    rightNode.next = null;
    //206题的逻辑 反转left到right的子链    reverseLinkedList(leftNode);
    //返乡连接    pre.next = rightNode;    leftNode.next = curr;    return dummyNode.next;};
const reverseLinkedList = (head) => {    let pre = null;    let cur = head;
    while (cur) {        const next = cur.next;        cur.next = pre;        pre = cur;        cur = next;    }}

class Solution {    public ListNode reverseBetween(ListNode head, int left, int right) {        ListNode dummyNode = new ListNode(-1);        dummyNode.next = head;
        ListNode pre = dummyNode        for (int i = 0; i < left - 1; i++) {            pre = pre.next;        }
        ListNode rightNode = pre;        for (int i = 0; i < right - left + 1; i++) {            rightNode = rightNode.next;        }
        ListNode leftNode = pre.next;        ListNode curr = rightNode.next;
        pre.next = null;        rightNode.next = null;
        reverseLinkedList(leftNode);
        pre.next = rightNode;        leftNode.next = curr;        return dummyNode.next;    }
    private void reverseLinkedList(ListNode head) {        ListNode pre = null;        ListNode cur = head;
        while (cur != null) {            ListNode next = cur.next;            cur.next = pre;            pre = cur;            cur = next;        }    }}

var reverseBetween = function(head, left, right) {    const dummy_node = new ListNode(-1);    dummy_node.next = head;//虚拟头节点    let pre = dummy_node;    for (let i = 0; i < left - 1; ++i) {//pre前进到left的前一个节点        pre = pre.next;    }
    let cur = pre.next;    for (let i = 0; i < right - left; ++i) {//循环right - left次 反转中间的节点        const next = cur.next;        cur.next = next.next;        next.next = pre.next;        pre.next = next;    }    return dummy_node.next;//返回虚拟头节点的next};

class Solution {    public ListNode reverseBetween(ListNode head, int left, int right) {        ListNode dummyNode = new ListNode(-1);        dummyNode.next = head;        ListNode pre = dummyNode;        for (int i = 0; i < left - 1; i++) {            pre = pre.next;        }        ListNode cur = pre.next;        ListNode next;        for (int i = 0; i < right - left; i++) {            next = cur.next;            cur.next = next.next;            next.next = pre.next;            pre.next = next;        }        return dummyNode.next;    }}

var swapPairs = function(head) {    if (head === null|| head.next === null) {//终止条件，必须要有两个节点        return head;    }    const newHead = head.next;//反转后链表的头节点，    head.next = swapPairs(newHead.next);//让当前递归层的head.next指向交换后返回的头节点    newHead.next = head;//让反转后的新的头节点指向当前层的head的节点    return newHead;//返回反转后的头节点};

class Solution {    public ListNode swapPairs(ListNode head) {        if (head == null || head.next == null) {            return head;        }        ListNode newHead = head.next;        head.next = swapPairs(newHead.next);        newHead.next = head;        return newHead;    }}

  temp.next = node2;  node1.next = node2.next;  node2.next = node1;

var swapPairs = function(head) {    const dummyHead = new ListNode(0);//虚拟头节点    dummyHead.next = head;//初始的时候让虚拟头节点指向head，    let temp = dummyHead;//temp指针    while (temp.next !== null && temp.next.next !== null) {//循环条件，dummyHead后存在至少两个节点        const node1 = temp.next;//node1指针，即dummyHead后的第一个节点        const node2 = temp.next.next;//node2指针，即dummyHead后的第二个节点        temp.next = node2;//下面三行是两两交换的核心代码        node1.next = node2.next;        node2.next = node1;        temp = node1;//后移一个节点的位置    }    return dummyHead.next;//返回交换后的头节点};

class Solution {    public ListNode swapPairs(ListNode head) {        ListNode dummyHead = new ListNode(0);        dummyHead.next = head;        ListNode temp = dummyHead;        while (temp.next != null && temp.next.next != null) {            ListNode node1 = temp.next;            ListNode node2 = temp.next.next;            temp.next = node2;            node1.next = node2.next;            node2.next = node1;            temp = node1;        }        return dummyHead.next;    }}

class ListNode {    constructor(key, value) {//双向链表的单个节点        this.key = key        this.value = value        this.next = null //指向后一个节点        this.prev = null //指向前一个节点    }}
class LRUCache {    constructor(capacity) {        this.capacity = capacity //容量        this.hashTable = {} //存放键值对信息        this.count = 0 //键值对数量        this.dummyHead = new ListNode() //dummy头节点 方便在链表从开始的地方插入        this.dummyTail = new ListNode()  //dummy尾节点 方便在链表从末尾删除        this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互连接        this.dummyTail.prev = this.dummyHead    }
    get(key) {        let node = this.hashTable[key]//查找哈希表中的键值对        if (node == null) return -1 //不存在该键值对 返回-1        this.moveToHead(node) //移动到链表头        return node.value    }
    put(key, value) {        let node = this.hashTable[key] //哈希表中查找该键值对        if (node == null) {            let newNode = new ListNode(key, value) //不存在就创建节点            this.hashTable[key] = newNode //加入哈希表            this.addToHead(newNode) //加入链表头            this.count++ //节点数+1            if (this.count > this.capacity) { //超过容量 从队尾删除一个                this.removeLRUItem()            }        } else {            node.value = value //键值对存在于哈希表中 就更新            this.moveToHead(node) //移动到队头        }    }
    moveToHead(node) {        this.removeFromList(node)//从链表中删除节点        this.addToHead(node)//将该节点添加到链表头    }
    removeFromList(node) {//删除的指针操作        let tempForPrev = node.prev        let tempForNext = node.next        tempForPrev.next = tempForNext        tempForNext.prev = tempForPrev    }
    addToHead(node) {//加入链表头的指针操作        node.prev = this.dummyHead        node.next = this.dummyHead.next        this.dummyHead.next.prev = node        this.dummyHead.next = node    }
    removeLRUItem() {        let tail = this.popTail()//从链表中删除        delete this.hashTable[tail.key]//从哈希表中删除        this.count--    }
    popTail() {        let tailItem = this.dummyTail.prev//通过dummyTail拿到最后一个节点 然后删除        this.removeFromList(tailItem)        return tailItem    }}

public class LRUCache {    class DLinkedNode {        int key;        int value;        DLinkedNode prev;        DLinkedNode next;        public DLinkedNode() {}        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}    }
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();    private int size;    private int capacity;    private DLinkedNode head, tail;
    public LRUCache(int capacity) {        this.size = 0;        this.capacity = capacity;
        head = new DLinkedNode();        tail = new DLinkedNode();        head.next = tail;        tail.prev = head;    }
    public int get(int key) {        DLinkedNode node = cache.get(key);        if (node == null) {            return -1;        }
        moveToHead(node);        return node.value;    }
    public void put(int key, int value) {        DLinkedNode node = cache.get(key);        if (node == null) {
            DLinkedNode newNode = new DLinkedNode(key, value);            cache.put(key, newNode);            addToHead(newNode);            ++size;            if (size > capacity) {                DLinkedNode tail = removeTail();                cache.remove(tail.key);                --size;            }        }        else {            node.value = value;            moveToHead(node);        }    }
    private void addToHead(DLinkedNode node) {        node.prev = head;        node.next = head.next;        head.next.prev = node;        head.next = node;    }
    private void removeNode(DLinkedNode node) {        node.prev.next = node.next;        node.next.prev = node.prev;    }
    private void moveToHead(DLinkedNode node) {        removeNode(node);        addToHead(node);    }
    private DLinkedNode removeTail() {        DLinkedNode res = tail.prev;        removeNode(res);        return res;    }}

var deleteNode = function(node) {    node.val = node.next.val//将要删除节点的下一个节点的值覆盖自己的值Ï    node.next = node.next.next//让当前节点指向下一个节点的next};

public void deleteNode(ListNode node) {    node.val = node.next.val;    node.next = node.next.next;}

var removeNthFromEnd = function (head, n) {    let dummy = new ListNode();    dummy.next = head;    let n1 = dummy;    let n2 = dummy;    for (let i = 0; i <= n; i++) {//n2移动n+1次        n2 = n2.next;    }    while (n2 !== null) {//同时移动n1，n2        n1 = n1.next;        n2 = n2.next;    }    n1.next = n1.next.next;//删除元素    return dummy.next;};

class Solution {    public ListNode removeNthFromEnd(ListNode head, int n) {        ListNode dummy = new ListNode(0);        dummy.next = head;        ListNode n1 = dummy;        ListNode n2 = dummy;        for (int i = 0; i <= n; i++) {//n2移动n次            n2 = n2.next;        }        while (n2 != null) {//同时移动n1，n2            n1 = n1.next;            n2 = n2.next;        }        n1.next = n1.next.next;//删除元素        return dummy.next;    }}

//例：0->1->2->3  val=2//level1: 0.next = removeElements(1, 2);      return 1          0->1->3->null//level2: 1.next = removeElements(2, 2);      return 3          1->3->null//level3: 2.next = removeElements(3, 2);      return 3          2->3->null//level4: 3.next = removeElements(null, 2);   return null;      3->null
var removeElements = function(head, val) {    if (head === null) {//递归终止 遍历完了链表      return head;    }    head.next = removeElements(head.next, val);//递归调用函数removeElements    return head.val === val ? head.next : head;//如果当前元素值是val，则返回下一个元素，否则直接返回当前元素};

class Solution {    public ListNode removeElements(ListNode head, int val) {        if (head == null) {            return head;        }        head.next = removeElements(head.next, val);        return head.val == val ? head.next : head;    }}

//2->1->2->3//dummy->2->1->2->3var removeElements = function(head, val) {    const dummyHead = new ListNode(0);//创建dummy节点，将dummy节点的next指向head，temp指向dummy    dummyHead.next = head;    let temp = dummyHead;    while (temp.next !== null) {//当temp的next不为null 不断循环节点        if (temp.next.val == val) {            temp.next = temp.next.next;//当temp的next值是要删除的 则删除该节点        } else {            temp = temp.next;//移动temp指针        }    }    return dummyHead.next;};

class Solution {    public ListNode removeElements(ListNode head, int val) {        ListNode dummyHead = new ListNode(0);        dummyHead.next = head;        ListNode temp = dummyHead;        while (temp.next != null) {            if (temp.next.val == val) {                temp.next = temp.next.next;            } else {                temp = temp.next;            }        }        return dummyHead.next;    }}

var addTwoNumbers = function(l1, l2) {    let head = null, tail = null;    let carry = 0;    while (l1 || l2) {//循环l1,l2链表        const n1 = l1 ? l1.val : 0;        const n2 = l2 ? l2.val : 0;        const sum = n1 + n2 + carry;//两链表节点相加在加进位        if (!head) {            head = tail = new ListNode(sum % 10);//当没有节点的时候新建节点        } else {            tail.next = new ListNode(sum % 10);//有节点的时候则加入tail节点的后面            tail = tail.next;        }        carry = Math.floor(sum / 10);//求进位        if (l1) {//移动l1指针            l1 = l1.next;        }        if (l2) {//移动l2指针            l2 = l2.next;        }    }    if (carry > 0) {//最后一位节点是否有进位        tail.next = new ListNode(carry);    }    return head;};

class Solution {    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {        ListNode head = null, tail = null;        int carry = 0;        while (l1 != null || l2 != null) {            int n1 = l1 != null ? l1.val : 0;            int n2 = l2 != null ? l2.val : 0;            int sum = n1 + n2 + carry;            if (head == null) {                head = tail = new ListNode(sum % 10);            } else {                tail.next = new ListNode(sum % 10);                tail = tail.next;            }            carry = sum / 10;            if (l1 != null) {                l1 = l1.next;            }            if (l2 != null) {                l2 = l2.next;            }        }        if (carry > 0) {            tail.next = new ListNode(carry);        }        return head;    }}

var mergeTwoLists = function(l1, l2) {  //递归终止 分隔到不能分割 也就是两个链表有一个的nxet不存在了 那就没法分割问题了 只能返回    if (l1 === null) {        return l2;    } else if (l2 === null) {        return l1;    } else if (l1.val < l2.val) {//当前节点谁小，就让这个较小的节点的next和另一个链表继续递归合并        l1.next = mergeTwoLists(l1.next, l2);//分隔成合并l1.next, l2的子问题        return l1;    } else {        l2.next = mergeTwoLists(l1, l2.next);        return l2;    }};

class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        if (l1 == null) {            return l2;        } else if (l2 == null) {            return l1;        } else if (l1.val < l2.val) {            l1.next = mergeTwoLists(l1.next, l2);            return l1;        } else {            l2.next = mergeTwoLists(l1, l2.next);            return l2;        }    }}

var mergeTwoLists = function(l1, l2) {    const prehead = new ListNode(-1);//虚拟头节点
    let prev = prehead;    while (l1 != null && l2 != null) {//循环两个链表        if (l1.val <= l2.val) {//小的节点接在prev的后面            prev.next = l1;            l1 = l1.next;//向后移动l1        } else {            prev.next = l2;//向后移动l2            l2 = l2.next;        }        prev = prev.next;////向后移动prev    }
    prev.next = l1 === null ? l2 : l1;//两个链表一个遍历完，另一个可能还没遍历完，没遍历完的接上
    return prehead.next;//返回prehead.next};

class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        ListNode prehead = new ListNode(-1);
        ListNode prev = prehead;        while (l1 != null && l2 != null) {            if (l1.val <= l2.val) {                prev.next = l1;                l1 = l1.next;            } else {                prev.next = l2;                l2 = l2.next;            }            prev = prev.next;        }
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;    }}

var deleteDuplicates = function(head) {    let cur = head;    while(cur && cur.next) {        if(cur.val == cur.next.val) {            cur.next = cur.next.next;        } else {            cur = cur.next;        }    }    return head;};

class Solution {    public ListNode deleteDuplicates(ListNode head) {        ListNode cur = head;        while(cur != null && cur.next != null) {            if(cur.val == cur.next.val) {                cur.next = cur.next.next;            } else {                cur = cur.next;            }        }        return head;    }}

var oddEvenList = function(head) {    if (head === null) {        return head;    }    let evenHead = head.next;    let odd = head, even = evenHead;    while (even !== null && even.next !== null) {//偶数指针不为空 继续循环        odd.next = even.next;//奇数指针指向偶数指针的next        odd = odd.next;//移动奇数指针        even.next = odd.next;//偶数指针指向奇数指针的next        even = even.next;//移动偶数指针    }    odd.next = evenHead;//奇数指针结尾连接上偶数指针的开始    return head;};

class Solution {    public ListNode oddEvenList(ListNode head) {        if (head == null) {            return head;        }        ListNode evenHead = head.next;        ListNode odd = head, even = evenHead;        while (even != null && even.next != null) {            odd.next = even.next;            odd = odd.next;            even.next = odd.next;            even = even.next;        }        odd.next = evenHead;        return head;    }}