小王爷

主题

LeetCode - 链表 ​

PS：按照代码随想录的题单顺序刷题，记录一下。

1. 基础概念 ​

见链表。

2. 移除链表元素 ​

描述

LeetCode203 - 给你一个链表的头节点 head 和一个整数 val，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点。简单

示例1：

txt
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
思路

这题思路很简单，遍历把目标元素删除即可，但代码并不好写，需要注意给定的结构没有头结点。

203 - 移除链表元素
javascript
var removeElements = function(head, val) {
  // 设置一个头节点便于统一操作
  const newHead = new ListNode();
  newHead.next = head;
  let current = newHead;
  while(current.next != null) {
    if (current.next.val == val) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return newHead.next;
};

3. 设计链表 ​

描述

LeetCode707 - 实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将不会插入到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。中等

示例1：

txt
输入：["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出：[null, null, null, null, 2, null, 3]
思路

属于链表基础，需要熟悉。

707 - 设计链表
javascript
var MyLinkedList = function() {
    this.head = undefined;
    this.count = 0;
};

const Node = function(element) {
    this.val = element;
    this.next = undefined;
}

/** 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
    if (index >= 0 && index < this.count) {
        let current = this.head;
        for(let i = 0; i < index; i++) {
            current = current.next;
        }
        return current.val;
    }
    return -1;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    const node = new Node(val);
    let current = this.head;
    node.next = current;
    this.head = node;
    this.count++;
    return true;
};

/** 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    const node = new Node(val);
    if (this.head == null) {
        this.head = node;
    } else {
        let current = this.head;
        while(current.next != null) {
            current = current.next;
        }
        current.next = node;
    }
    this.count++;
    return true;
};

/** 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
    const node = new Node(val);
    if(index >= 0 && index <= this.count) {
        if (index == 0) {
            node.next = this.head;
            this.head = node;
        } else {
            let current = this.head;
            let previous;
            for(let i = 0; i < index; i++) {
                previous = current;
                current = current.next;
            }
            node.next = current;
            previous.next = node
        }
        this.count++;
        return true;
    }
    return false;
};

/** 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
    if (index >= 0 && index < this.count) {
        if (index == 0) {
            this.head = this.head.next;
        } else {
            let current = this.head;
            let previous;
            for(let i = 0; i < index; i++) {
                previous = current;
                current = current.next;
            }
            previous.next = current.next;
        }
        this.count--;
        return true;
    } 
    return false
};

4. 反转链表 ​

描述

LeetCode206 - 给你单链表的头节点 head，请你反转链表，并返回反转后的链表。简单

示例1：

txt
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
思路

构造个新链表，依次遍历并将元素插入新链表的第一个位置。

双指针：使用两个指针分别保存上一元素和下一元素。

206 - 反转链表
javascript
var reverseList = function(head) {
    if(!head) return null;
    let list = new ListNode(head.val, null);
    let current = head.next;
    while(current) {
        const node = new ListNode(current.val, null);
        node.next = list;
        list = node;
        current = current.next;
    }
    return list;
};

// 双指针
var reverseList = function(head) {
    if(!head) return head;
    let prev = null, after, current = head;
    while(current) {
        after = current.next;
        current.next = prev;
        prev = current;
        current = after;
    }
    return prev;
};

5. 两两交换链表中的节点 ​

描述

LeetCode24 - 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即只能进行节点交换）。中等

示例1：

txt
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例2：

txt
输入：head = []
输出：[]
思路

依次遍历，两个两个元素的比较，如果后面不存在两个元素则结束循环，存在则交换位置，可以创建个虚拟头节点来统一操作。

24 - 两两交换链表中的节点
javascript
// 虚拟节点
var swapPairs = function(head) {
    if(!head || !head.next) return head;
    // 使用头节点统一操作节点后两个元素
    const res = new ListNode();
    res.next = head;
    let current = res, first, second;
    while(current.next) {
        first = current.next;
        second = current.next.next;
        if (second) {
            first.next = second.next;
            second.next = first;
            current.next = second;
            current = first;
        } else {
            break;
        }
    }
    return res.next;
};

6. 删除链表的倒数第 N 个结点 ​

描述

LeetCode19 - 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。中等

示例1：

txt
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例2：

txt
输入：head = [1], n = 1
输出：[]
思路

定义双指针，右指针先前进 n 步，左指针再跟着遍历，当右指针遍历到末尾时，左指针指向的就是要删除的元素的前一节点。大多数链表题可以设置虚拟头节点，便于操作。

19 - 删除链表的倒数第 N 个结点
javascript
var removeNthFromEnd = function(head, n) {
    const dummy = new ListNode();
    dummy.next = head;
    // 双指针
    let left = dummy, right = dummy;
    for(i = 0; i < n; i++) {
        right = right.next;
    }
    while(right.next) {
        right = right.next;
        left = left.next
    }
    left.next = left.next.next;
    return dummy.next;
};

7. 相交链表 ​

描述

LeetCode160 - 给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。简单

示例1：

txt
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
思路

哈希表：使用哈希表存储一个链表的元素，遍历另一链表判断是否有相同节点。

双指针：分别遍历两个链表并比较，到达最后一个元素将指针指向另一个链表。

160 - 相交链表
javascript
// 双指针
var getIntersectionNode = function (headA, headB) {
    let currentA = headA, currentB = headB;
    let transforA = true, transforB = true;
    while (currentA && currentB) {
        if (currentA === currentB) {
            return currentA;
        }
        currentA = currentA.next;
        currentB = currentB.next;
        if (transforA && !currentA) {
            currentA = headB;
            transforA = false;
        }
        if(transforB && !currentB) {
            currentB = headA;
            transforB = false;
        }
    }
    return null;
};

// 哈希表
var getIntersectionNode = function(headA, headB) {
    const map = new Map();
    let current = headA;
    while(current) {
        map.set(current, 1);
        current = current.next;
    }
    current = headB;
    while(current) {
        if(map.has(current)) {
            return current;
        }
        current = current.next;
    }
    return null;
};

8. 环形链表II ​

描述

LeetCode142 - 给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。中等

示例1：

txt
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。pos 表示尾部指向的节点索引，为 -1 表示无环。
思路

首先想到的就是用哈希表或集合将遍历过的节点保存，时间和空间复杂度都是 O(n)。还有个快慢指针版本，其中快指针每次走两步，慢指针每次一步，二者必定会在环内相遇（这里可能不好理解），经过数学推理可以得出，慢指针从环内相遇点继续向下走，同时用第三个指针从头指针开始出发，二者相遇的节点就是开始入环的节点。

142 - 环形链表II
javascript
// 哈希表
var detectCycle = function(head) {
    const map = new Map();
    let current = head;
    while(current) {
        if (map.get(current)) {
            return current;
        }
        map.set(current, 1);
        current = current.next;
    }
    return null;
};

// 快慢指针
var detectCycle = function(head) {
    if (!head) return null;
    let slow = head, fast = head;
    while(fast) {
        slow = slow.next;
        if(!fast.next) {
            return null;
        } else {
            fast = fast.next.next;
        }
        if(fast === slow) {
            let cur = head;
            while(cur !== slow) {
                cur = cur.next;
                slow = slow.next;
            }
            return cur;
        }
    }
    return null;
};

最后更新于: