大廠算法面試之leetcode精講15.鏈表

視頻講解（高效學(xué)習(xí)）:點(diǎn)擊學(xué)習(xí)

目錄：

1.開篇介紹

2.時(shí)間空間復(fù)雜度

3.動(dòng)態(tài)規(guī)劃

4.貪心

5.二分查找

6.深度優(yōu)先&廣度優(yōu)先

7.雙指針

8.滑動(dòng)窗口

9.位運(yùn)算

10.遞歸&分治

11剪枝&回溯

12.堆

13.單調(diào)棧

14.排序算法

15.鏈表

16.set&map

17.棧

18.隊(duì)列

19.數(shù)組

20.字符串

21.樹

22.字典樹

23.并查集

24.其他類型題

鏈表操作如下圖：

動(dòng)畫過大，點(diǎn)擊查看

時(shí)間復(fù)雜度：

• prepend: O(1)
• append: 如果已知尾節(jié)點(diǎn)O(1)，否則需要遍歷到尾節(jié)點(diǎn)，然后加入新節(jié)點(diǎn)O(n)
• insert: 插入到已知節(jié)點(diǎn)的后面O(1)，需要先查找后插入O(n)
• lookup: O(n)
• Delete：刪除已知節(jié)點(diǎn)O(1)，需要先查找后刪除O(n)

206. 反轉(zhuǎn)鏈表（easy）

方法1.頭插法：

動(dòng)畫過大，點(diǎn)擊查看

• 思路：準(zhǔn)備一個(gè)臨時(shí)節(jié)點(diǎn)，然后遍歷鏈表，準(zhǔn)備兩個(gè)指針head和next，每次循環(huán)到一個(gè)節(jié)點(diǎn)的時(shí)候，將head.next指向temp.next，并且將temp.next指向head，head和next向后移一位。
• 復(fù)雜度分析：時(shí)間復(fù)雜度：O(n)， n為鏈表節(jié)點(diǎn)數(shù)，空間復(fù)雜度：O(1)

js:

var reverseList = function (head) {
  let temp = new ListNode();
  let next = null;
  while (head) {
    next = head.next;//下一個(gè)節(jié)點(diǎn)
    head.next = temp.next;
    temp.next = head;//head接在temp的后面
    head = next;//head向后移動(dòng)一位
  }
  return temp.next;
};

方法2.迭代法：

動(dòng)畫過大，點(diǎn)擊查看

• 思路: 遍歷鏈表，準(zhǔn)備prev，curr，next三個(gè)指針，在遍歷的過程中，讓當(dāng)前指針curr.next指向前一個(gè)指針prev，然后不斷讓prev，curr，next向后移動(dòng)，直到curr為null
• 復(fù)雜度分析：時(shí)間復(fù)雜度：O(n)， n為鏈表節(jié)點(diǎn)數(shù)，空間復(fù)雜度：O(1)

js：

var reverseList = function (head) {
  let prev = null;
  let curr = head;
  let next = null;
  while (curr !== null) {
    next = curr.next;//next向后移動(dòng)一位
    curr.next = prev;//讓當(dāng)前指針curr.next指向前一個(gè)指針prev
    prev = curr;//prev向后移動(dòng)一位
    curr = next;//curr向后移動(dòng)一位
    //[curr.next, prev, curr] = [prev, curr, curr.next]
  }
  return prev;
};

java：

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;
    }
}

方法3.遞歸：

動(dòng)畫過大，點(diǎn)擊查看

• 思路：用遞歸函數(shù)不斷傳入head.next，直到head==null或者heade.next==null，到了遞歸最后一層的時(shí)候，讓后面一個(gè)節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)，然后讓前一個(gè)節(jié)點(diǎn)的next置為空，直到到達(dá)第一層，就是鏈表的第一個(gè)節(jié)點(diǎn)，每一層都返回最后一個(gè)節(jié)點(diǎn)。
• 復(fù)雜度分析：時(shí)間復(fù)雜度：O(n)，n是鏈表的長(zhǎng)度。空間復(fù)雜度：O(n)， n是遞歸的深度，遞歸占用?？臻g，可能會(huì)達(dá)到n層

js:

var reverseList = function(head) {
    if (head == null || head.next == null) {//遞歸終止條件
        return head;
    }
    const newHead = reverseList(head.next);//遞歸調(diào)用reverseList
    head.next.next = head;//到了遞歸最后一層的時(shí)候，讓后面一個(gè)節(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)
    head.next = null;//前一個(gè)節(jié)點(diǎn)的next置為空
    return newHead;//返回最后一個(gè)節(jié)點(diǎn)
};

Java:

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;
    }
}

92. 反轉(zhuǎn)鏈表 II(medium)

方法1

動(dòng)畫過大，點(diǎn)擊查看

• 思路：切斷l(xiāng)eft到right的子鏈，然后反轉(zhuǎn)，最后在反向連接
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js：

var reverseBetween = function(head, left, right) {
    const dummyNode = new ListNode(-1);
    dummyNode.next = head;//虛擬頭節(jié)點(diǎn)

    let pre = dummyNode;
    for (let i = 0; i < left - 1; i++) {//pre遍歷到left的前一個(gè)節(jié)點(diǎn)
        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

    //切斷l(xiāng)eft到right的子鏈
    pre.next = null;
    rightNode.next = null;

        //206題的邏輯 反轉(zhuǎn)left到right的子鏈
    reverseLinkedList(leftNode);

    //返鄉(xiāng)連接
    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;
    }
}

java：

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;
        }
    }
}

方法2

動(dòng)畫過大，點(diǎn)擊查看

• 思路：從left遍歷到right，在遍歷的過程中反轉(zhuǎn)鏈表
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js：

var reverseBetween = function(head, left, right) {
    const dummy_node = new ListNode(-1);
    dummy_node.next = head;//虛擬頭節(jié)點(diǎn)
    let pre = dummy_node;
    for (let i = 0; i < left - 1; ++i) {//pre前進(jìn)到left的前一個(gè)節(jié)點(diǎn)
        pre = pre.next;
    }

    let cur = pre.next;
    for (let i = 0; i < right - left; ++i) {//循環(huán)right - left次 反轉(zhuǎn)中間的節(jié)點(diǎn)
        const next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return dummy_node.next;//返回虛擬頭節(jié)點(diǎn)的next
};

java：

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;
    }
}

24. 兩兩交換鏈表中的節(jié)點(diǎn) （medium）

方法1.遞歸：

ds_17

• 思路：用遞歸函數(shù)不斷傳入鏈表的下一個(gè)節(jié)點(diǎn)，終止條件是head === null|| head.next === null，也就是至少存在兩個(gè)節(jié)點(diǎn)進(jìn)行兩兩交換，在最后一層的時(shí)候開始兩兩反轉(zhuǎn)，讓當(dāng)前遞歸層的head.next指向交換后返回的頭節(jié)點(diǎn)，然后讓反轉(zhuǎn)后的新的頭節(jié)點(diǎn)指向當(dāng)前層的head的節(jié)點(diǎn)，這樣就實(shí)現(xiàn)了兩兩交換，最后返回反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)
• 復(fù)雜的分析：時(shí)間復(fù)雜度O(n)， n 是鏈表的節(jié)點(diǎn)數(shù)量?？臻g復(fù)雜度O(n)，n是遞歸調(diào)用的?？臻g

js:

var swapPairs = function(head) {
    if (head === null|| head.next === null) {//終止條件，必須要有兩個(gè)節(jié)點(diǎn)
        return head;
    }
    const newHead = head.next;//反轉(zhuǎn)后鏈表的頭節(jié)點(diǎn)，
    head.next = swapPairs(newHead.next);//讓當(dāng)前遞歸層的head.next指向交換后返回的頭節(jié)點(diǎn)
    newHead.next = head;//讓反轉(zhuǎn)后的新的頭節(jié)點(diǎn)指向當(dāng)前層的head的節(jié)點(diǎn)
    return newHead;//返回反轉(zhuǎn)后的頭節(jié)點(diǎn)
};

Java:

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;
    }
}

方法2.循環(huán)(虛擬頭節(jié)點(diǎn))

ds_18

• 思路：設(shè)置虛擬頭節(jié)點(diǎn)dummyHead，讓dummyHead.next指向head,當(dāng)temp.next !== null && temp.next.next !== null的時(shí)候，也就是dummyHead后面存在至少兩個(gè)節(jié)點(diǎn)，才開始兩兩交換節(jié)點(diǎn)。交換之前準(zhǔn)備三個(gè)指針temp指向dummyHead，node1是dummyHead后面的第一個(gè)節(jié)點(diǎn)，node2是dummyHead后的第二個(gè)節(jié)點(diǎn)，交換的時(shí)候讓temp.next指向node2，node1.next指向node2.next，node2.next指向node1，每次循環(huán)迭代讓這三個(gè)節(jié)點(diǎn)后移一個(gè)節(jié)點(diǎn)，最后返回dummyHead.next，核心步驟是

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

• 復(fù)雜的分析：時(shí)間復(fù)雜度O(n)， n 是鏈表的節(jié)點(diǎn)數(shù)量?？臻g復(fù)雜度O(1)，

Js:

var swapPairs = function(head) {
    const dummyHead = new ListNode(0);//虛擬頭節(jié)點(diǎn)
    dummyHead.next = head;//初始的時(shí)候讓虛擬頭節(jié)點(diǎn)指向head，
    let temp = dummyHead;//temp指針
    while (temp.next !== null && temp.next.next !== null) {//循環(huán)條件，dummyHead后存在至少兩個(gè)節(jié)點(diǎn)
        const node1 = temp.next;//node1指針，即dummyHead后的第一個(gè)節(jié)點(diǎn)
        const node2 = temp.next.next;//node2指針，即dummyHead后的第二個(gè)節(jié)點(diǎn)
        temp.next = node2;//下面三行是兩兩交換的核心代碼
        node1.next = node2.next;
        node2.next = node1;
        temp = node1;//后移一個(gè)節(jié)點(diǎn)的位置
    }
    return dummyHead.next;//返回交換后的頭節(jié)點(diǎn)
};

Java:

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;
    }
}

146. LRU 緩存機(jī)制 （medium）

ds_19

ds_212

• 思路：準(zhǔn)備一個(gè)哈希表和雙向鏈表存儲(chǔ)鍵值對(duì)，哈希表O(1)就能查找到鍵值對(duì)，雙向鏈表方便從鏈表頭部新增節(jié)點(diǎn)，也可以從隊(duì)尾刪除節(jié)點(diǎn)

  1. get的時(shí)候，查找哈希表中有沒有該鍵值對(duì)，不存在就返回-1，存在就返回該節(jié)點(diǎn)的值，并且將該節(jié)點(diǎn)移動(dòng)到鏈表的頭部
  2. put的時(shí)候，查找哈希表中有沒有該鍵值對(duì)，如果存在就更新該節(jié)點(diǎn)，并且移動(dòng)到鏈表的頭部，不存在就創(chuàng)建一個(gè)節(jié)點(diǎn)，加入到哈希表和鏈表的頭部，并且讓節(jié)點(diǎn)數(shù)count+1，如果超出容量，就從隊(duì)尾刪除一個(gè)節(jié)點(diǎn)

• 復(fù)雜度：put、get時(shí)間復(fù)雜度都是O(1)，空間復(fù)雜度O(c)，c是LRU的容量

js:

class ListNode {
    constructor(key, value) {//雙向鏈表的單個(gè)節(jié)點(diǎn)
        this.key = key
        this.value = value
        this.next = null //指向后一個(gè)節(jié)點(diǎn)
        this.prev = null //指向前一個(gè)節(jié)點(diǎn)
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity //容量
        this.hashTable = {} //存放鍵值對(duì)信息
        this.count = 0 //鍵值對(duì)數(shù)量
        this.dummyHead = new ListNode() //dummy頭節(jié)點(diǎn) 方便在鏈表從開始的地方插入
        this.dummyTail = new ListNode() //dummy尾節(jié)點(diǎn) 方便在鏈表從末尾刪除
        this.dummyHead.next = this.dummyTail //dummyHead和dummyTail相互連接
        this.dummyTail.prev = this.dummyHead
    }

    get(key) {
        let node = this.hashTable[key]//查找哈希表中的鍵值對(duì)
        if (node == null) return -1 //不存在該鍵值對(duì) 返回-1
        this.moveToHead(node) //移動(dòng)到鏈表頭
        return node.value
    }

    put(key, value) {
        let node = this.hashTable[key] //哈希表中查找該鍵值對(duì)
        if (node == null) {
            let newNode = new ListNode(key, value) //不存在就創(chuàng)建節(jié)點(diǎn)
            this.hashTable[key] = newNode //加入哈希表
            this.addToHead(newNode) //加入鏈表頭
            this.count++ //節(jié)點(diǎn)數(shù)+1
            if (this.count > this.capacity) { //超過容量 從隊(duì)尾刪除一個(gè)
                this.removeLRUItem()
            }
        } else {
            node.value = value //鍵值對(duì)存在于哈希表中 就更新
            this.moveToHead(node) //移動(dòng)到隊(duì)頭
        }
    }

    moveToHead(node) {
        this.removeFromList(node)//從鏈表中刪除節(jié)點(diǎn)
        this.addToHead(node)//將該節(jié)點(diǎn)添加到鏈表頭
    }

    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拿到最后一個(gè)節(jié)點(diǎn) 然后刪除
        this.removeFromList(tailItem)
        return tailItem
    }
}

Java:

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;
    }
}

237. 刪除鏈表中的節(jié)點(diǎn)（easy）

ds_125

• 思路：將要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的值覆蓋自己的值，然后讓當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)的next
• 復(fù)雜度：時(shí)間復(fù)雜度和空間復(fù)雜度都是O(1)

js：

var deleteNode = function(node) {
    node.val = node.next.val//將要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的值覆蓋自己的值?
    node.next = node.next.next//讓當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn)的next
};

java；

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

19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn) (medium)

方法1：棧

• 思路：循環(huán)鏈表，將所有的節(jié)點(diǎn)入棧，然后在彈出棧n次，就是我們需要?jiǎng)h除的節(jié)點(diǎn)
• 復(fù)雜度：時(shí)間復(fù)雜度O(L)，L是鏈表的長(zhǎng)度，空間復(fù)雜度O(L)。

方法2:遍歷2次

• 思路：遍歷一次鏈表的到鏈表的長(zhǎng)度L，在重頭遍歷到L-n+1的位置就是需要?jiǎng)h除的節(jié)點(diǎn)。
• 復(fù)雜度：時(shí)間復(fù)雜度O(L)，L是鏈表的長(zhǎng)度，空間復(fù)雜度O(1)

方法3:遍歷1次

動(dòng)畫過大，點(diǎn)擊查看

• 思路：新建dummy節(jié)點(diǎn)指向head，指針n1，n2指向head，循環(huán)n2指針到n的位置，然后在同時(shí)移動(dòng)n1，n2，直到結(jié)尾，n1，n2的距離是n，此時(shí)n1的位置就是需要?jiǎng)h除元素的位置
• 復(fù)雜度：時(shí)間復(fù)雜度O(L)，L是鏈表的長(zhǎng)度，空間復(fù)雜度O(1)

js:

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移動(dòng)n+1次
        n2 = n2.next;
    }
    while (n2 !== null) {//同時(shí)移動(dòng)n1，n2
        n1 = n1.next;
        n2 = n2.next;
    }
    n1.next = n1.next.next;//刪除元素
    return dummy.next;
};

java:

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移動(dòng)n次
            n2 = n2.next;
        }
        while (n2 != null) {//同時(shí)移動(dòng)n1，n2
            n1 = n1.next;
            n2 = n2.next;
        }
        n1.next = n1.next.next;//刪除元素
        return dummy.next;
    }
}

203. 移除鏈表元素 (easy)

方法1.遞歸

• 思路：遞歸調(diào)用函數(shù)removeElements，傳入head.next和 val，如果當(dāng)前元素值是val，則返回下一個(gè)元素，否則直接返回當(dāng)前元素
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，n是鏈表的長(zhǎng)度，空間復(fù)雜度是O(n)，遞歸棧的深度，最大為n

js：

//例：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);//遞歸調(diào)用函數(shù)removeElements
    return head.val === val ? head.next : head;//如果當(dāng)前元素值是val，則返回下一個(gè)元素，否則直接返回當(dāng)前元素
};

java：

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.迭代

• 思路：創(chuàng)建dummy節(jié)點(diǎn)，將dummy節(jié)點(diǎn)的next指向head，temp指向dummy，當(dāng)temp的next不為null 不斷移動(dòng)temp指針，當(dāng)temp的next值是要?jiǎng)h除的 則刪除該節(jié)點(diǎn)
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，n是鏈表的長(zhǎng)度，空間復(fù)雜度是O(1)

js：

//2->1->2->3
//dummy->2->1->2->3
var removeElements = function(head, val) {
    const dummyHead = new ListNode(0);//創(chuàng)建dummy節(jié)點(diǎn)，將dummy節(jié)點(diǎn)的next指向head，temp指向dummy
    dummyHead.next = head;
    let temp = dummyHead;
    while (temp.next !== null) {//當(dāng)temp的next不為null 不斷循環(huán)節(jié)點(diǎn)
        if (temp.next.val == val) {
            temp.next = temp.next.next;//當(dāng)temp的next值是要?jiǎng)h除的 則刪除該節(jié)點(diǎn)
        } else {
            temp = temp.next;//移動(dòng)temp指針
        }
    }
    return dummyHead.next;
};

java：

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;
    }
}

2. 兩數(shù)相加 （medium）

ds_166

• 思路：循環(huán)兩個(gè)鏈表，計(jì)算每個(gè)節(jié)點(diǎn)相加的和在加進(jìn)位，然后計(jì)算進(jìn)位，處理最后一次的進(jìn)位。
• 復(fù)雜度：時(shí)間復(fù)雜度O(max(m，n))，循環(huán)的次數(shù)是鏈表較長(zhǎng)的那個(gè)?？臻g復(fù)雜度O(1)

js：

var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let carry = 0;
    while (l1 || l2) {//循環(huán)l1,l2鏈表
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1 + n2 + carry;//兩鏈表節(jié)點(diǎn)相加在加進(jìn)位
        if (!head) {
            head = tail = new ListNode(sum % 10);//當(dāng)沒有節(jié)點(diǎn)的時(shí)候新建節(jié)點(diǎn)
        } else {
            tail.next = new ListNode(sum % 10);//有節(jié)點(diǎn)的時(shí)候則加入tail節(jié)點(diǎn)的后面
            tail = tail.next;
        }
        carry = Math.floor(sum / 10);//求進(jìn)位
        if (l1) {//移動(dòng)l1指針
            l1 = l1.next;
        }
        if (l2) {//移動(dòng)l2指針
            l2 = l2.next;
        }
    }
    if (carry > 0) {//最后一位節(jié)點(diǎn)是否有進(jìn)位
        tail.next = new ListNode(carry);
    }
    return head;
};

java：

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;
    }
}

21. 合并兩個(gè)有序鏈表 (easy)

方法1.遞歸

ds_167

• 思路：遞歸合并節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)誰小，就讓這個(gè)較小的節(jié)點(diǎn)的next和另一個(gè)鏈表繼續(xù)遞歸合并，直到兩個(gè)鏈表有一個(gè)的nxet不存在了，那就沒法分割問題了，只能返回
• 復(fù)雜度：時(shí)間復(fù)雜度O(m+n)，m、n為兩個(gè)鏈表的長(zhǎng)度，每次遞歸排除掉一個(gè)節(jié)點(diǎn)，總遞歸次數(shù)是m+n?？臻g復(fù)雜度O(m+n)，遞歸?？臻g

js：

var mergeTwoLists = function(l1, l2) {
  //遞歸終止 分隔到不能分割 也就是兩個(gè)鏈表有一個(gè)的nxet不存在了 那就沒法分割問題了 只能返回
    if (l1 === null) {
        return l2;
    } else if (l2 === null) {
        return l1;
    } else if (l1.val < l2.val) {//當(dāng)前節(jié)點(diǎn)誰小，就讓這個(gè)較小的節(jié)點(diǎn)的next和另一個(gè)鏈表繼續(xù)遞歸合并
        l1.next = mergeTwoLists(l1.next, l2);//分隔成合并l1.next, l2的子問題
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

java：

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;
        }
    }
}

方法2.迭代

動(dòng)畫過大，點(diǎn)擊查看

• 思路：設(shè)立虛擬頭節(jié)點(diǎn)prehead，prev節(jié)點(diǎn)初始指向prehead，循環(huán)兩個(gè)鏈表，兩個(gè)鏈表中小的節(jié)點(diǎn)接在prev的后面，不斷移動(dòng)prev，最后返回prehead.next
• 復(fù)雜度：時(shí)間復(fù)雜度O(m+n)，m、n為兩個(gè)鏈表的長(zhǎng)度，循環(huán)m+n次。空間復(fù)雜度O(1)

js：

var mergeTwoLists = function(l1, l2) {
    const prehead = new ListNode(-1);//虛擬頭節(jié)點(diǎn)

    let prev = prehead;
    while (l1 != null && l2 != null) {//循環(huán)兩個(gè)鏈表
        if (l1.val <= l2.val) {//小的節(jié)點(diǎn)接在prev的后面
            prev.next = l1;
            l1 = l1.next;//向后移動(dòng)l1
        } else {
            prev.next = l2;//向后移動(dòng)l2
            l2 = l2.next;
        }
        prev = prev.next;////向后移動(dòng)prev
    }

    prev.next = l1 === null ? l2 : l1;//兩個(gè)鏈表一個(gè)遍歷完，另一個(gè)可能還沒遍歷完，沒遍歷完的接上

    return prehead.next;//返回prehead.next
};

java：

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;
    }
}

83. 刪除排序鏈表中的重復(fù)元素 (easy)

時(shí)間復(fù)雜度：O(n)?？臻g復(fù)雜度O(1)

js:

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;
};

java:

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;
    }
}

328. 奇偶鏈表 (medium)

動(dòng)畫過大，點(diǎn)擊查看

• 思路：奇偶指針循環(huán)鏈表，奇數(shù)指針不斷串連奇數(shù)節(jié)點(diǎn)，偶數(shù)指針不斷串連偶數(shù)節(jié)點(diǎn)，最后奇數(shù)指針的結(jié)尾連接偶數(shù)節(jié)點(diǎn)的開始
• 復(fù)雜度：時(shí)間復(fù)雜度O(n)，空間復(fù)雜度O(1)

js：

var oddEvenList = function(head) {
    if (head === null) {
        return head;
    }
    let evenHead = head.next;
    let odd = head, even = evenHead;
    while (even !== null && even.next !== null) {//偶數(shù)指針不為空 繼續(xù)循環(huán)
        odd.next = even.next;//奇數(shù)指針指向偶數(shù)指針的next
        odd = odd.next;//移動(dòng)奇數(shù)指針
        even.next = odd.next;//偶數(shù)指針指向奇數(shù)指針的next
        even = even.next;//移動(dòng)偶數(shù)指針
    }
    odd.next = evenHead;//奇數(shù)指針結(jié)尾連接上偶數(shù)指針的開始
    return head;
};

java：

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;
    }
}