@[toc]

序号为LeetCode的题序，语言选择的是JavaScript

707. 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/design-linked-list

/**
 * Initialize your data structure here.
 * 初始化数据结构
 */
var MyLinkedList = function () {
  // 初始化 链表长度 和 头指针
  this.length = 0;
  this.head = null;
};

/**
 * 初始化链表中的节点
 * @param {*} val
 */
MyLinkedList.prototype.node = function (val) {
  this.val = val;
  this.next = null;
};

/**
 * Get the value of the index-th node in the linked list. If the index is invalid, return -1.
 * 获取链表中第 index 个节点的值。如果索引无效，则返回-1
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
  if (index < 0 || index >= this.length) {
    return -1;
  }

  // 从头结点开始遍历
  let current = this.head;
  for (let i = 0; i < index; i++) {
    current = current.next;
  }

  return current ? current.val : -1;
};

/**
 * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
 * 在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  // 新建一个节点，将值val传递进去
  let headNode = new this.node(val);
  // 将新建的节点的next指向当前链表头结点
  headNode.next = this.head;
  // 将链表头结点指针指向新建的节点
  this.head = headNode;
  // 链表长度增加
  this.length++;
};

/**
 * Append a node of value val to the last element of the linked list.
 * 将值为 val 的节点追加到链表的最后一个元素
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  // 新建尾结点
  let tailNode = new this.node(val);

  // 遍历到链表当前尾节点
  let current = this.head;

  while (current && current.next) {
    current = current.next;
  }

  if (current) {
    current.next = tailNode;
  } else {
    current = tailNode;
    this.head = tailNode;
  }

  this.length++;
};

/**
 * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
 * 在链表中的第 index 个节点之前添加值为 val  的节点。
 * 如果 index 等于链表的长度，则该节点将附加到链表的末尾。
 * 如果 index 大于链表长度，则不会插入节点。
 * 如果index小于0，则在头部插入节点。
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  if (index <= 0) return this.addAtHead(val);
  if (index === this.length) return this.addAtTail(val);
  if (index > this.length) return;

  let addNode = new this.node(val);

  // 找到index位置的前一个节点
  let prev = this.head;
  for (let i = 0; i < index - 1; i++) {
    prev = prev.next;
  }

  // 添加节点操作
  addNode.next = prev.next;
  prev.next = addNode;

  this.length++;
};

/**
 * Delete the index-th node in the linked list, if the index is valid.
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  if (index < 0 || index >= this.length) return;
  if (index === 0) {
    this.head = this.head.next;
    this.length--;
  } else {
    // 找到index前一个节点
    let prev = this.head;
    for (let i = 0; i < index - 1; i++) {
      prev = prev.next;
    }

    // 删除节点
    if (prev && prev.next) {
      prev.next = prev.next.next;
    }

    this.length--;
  }
};

2. 两数相加

https://leetcode-cn.com/problems/add-two-numbers/ (opens new window)

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
	// 创建两个指针，一个指向链表头部一个空的0节点，一个指向尾部
    let head = new ListNode(0)
    let tail = head
	// 进位计数变量
    let add = 0
	// 只要两个链表有一个不为空就一直循环
    while(l1 || l2){
    	// 如果有一个遍历结束了，后面都置0
        let num1 = l1 ? l1.val : 0
        let num2 = l2 ? l2.val : 0
        
        // 两数之和，加上进位
        let sum = num1 + num2 + add

		// 如果求和超过10，就要进位，add就是进位的数字
        add = Math.floor(sum/10)
        // sum小于10就还是自己，超过10就是个位
        sum = sum % 10
        // 在尾指针后添加新节点
        tail.next = new ListNode(sum)
		// 尾指针后移
        tail = tail.next
        
		// 只要传入的链表还有元素就一直遍历
        if(l1) l1 = l1.next
        if(l2) l2 = l2.next
    }
	// 遍历结束，如果最后还有一个进位，就把他添加到最后
    if(add === 1){
        tail.next = new ListNode(add)
    }
	// 最后返回头节点的后一个节点就是所求的链表
    return head.next
};

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

双指针

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let left = head
    let right = head
    for(let i = 0; i < k; i++){
        right = right.next
    }
    while(right){
        right = right.next
        left = left.next
    }
    return left
};

141. 环形链表

给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 如果链表中存在环，则返回 true 。 否则，返回 false 。

【解法一 JS特性】

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    try{
        JSON.stringify(head)
    }catch(e){
        return true
    }
    return false
};

【解法二】使用Map

var hasCycle = function(head) {
    let map = new Map()
    while(head) {
        if(map.has(head)) return true
        map.set(head, true)
        head = head.next
    }
    return false
};

【解法三】快慢指针

var hasCycle = function(head) {
    let fast = head
    let slow = head
    while(fast){
        if(fast.next === null) return false
        slow = slow.next
        fast = fast.next.next
        if(slow === fast) return true
    }
    return false
};

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 说明：不允许修改给定的链表。

【解法一】使用Map

var detectCycle = function(head) {
    let map = new Map()
    while(head){
        if(map.has(head)){
            return head;
        }
        map.set(head, true)
        head = head.next
    }
    return null
};

【解法二】快慢指针

var detectCycle = function(head) {
    if(head === null) return null
    let slow = head
    let fast = head
    while(fast){
        if(fast.next===null) return null
        slow = slow.next
        fast = fast.next.next
        if(slow === fast){
            let pre = head
            while(slow !== pre){
                pre = pre.next
                slow = slow.next
            }
            return pre
        }
    }
    return null
};

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

【解法一】使用Map

var getIntersectionNode = function(headA, headB) {
    if(headA === null || headB === null) return null
    let map = new Map()
    let a = headA
    let b = headB
    while(a){
        map.set(a, true)
        a = a.next
    }
    while(b){
        if(map.has(b)){
            return b
        }
        b = b.next
    }
    return null
};

【解法二】双指针

将两个链表拼在一起，就可以同时到达相交的地方了

var getIntersectionNode = function(headA, headB) {
    if(headA === null || headB === null) return null

    let a = headA
    let b = headB

    while(a!== b){
        a = a.next;
        b = b.next;
        if(a === null && b === null) return null
        // a遍历完了就把b链表接后面
        if(a === null){
            a = headB
        }
        // b遍历完了就把a链表接后面
        if(b === null){
            b = headA
        }
    }
    // a指针和b指针相同 null或者具体结点
    return a
};

21. 合并两个有序链表

迭代

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
 
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function (l1, l2) {
  const prehead = new ListNode(-1);
  let 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;
  }

  if (l1 === null) {
    prev.next = l2;
  } else{
    prev.next = l1;
  }

  return prehead.next;
};

递归

首先找到递归终止条件出口，就是一方元素为空，返回另一方

if(l1 === null){
    return l2
}else if(l2 === null){
    return l1
}

然后进行一般的判断 将头结点小的那个指针

if(l1.val < l2.val){
	l1.next = mergeTwoLists(l1.next, l2)
	return l1;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, 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
    }
};

237. 删除链表中的节点

注意题目给的条件，没有传入head，所以是直接对传入的node进行操作的

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
};

剑指 Offer 24. 反转链表

【解法一】非递归

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr) {
        let temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }
    return prev;
};

【解法二】递归

var reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;
    }
    const newHead = reverseList(head.next);
    
    head.next.next = head;
    head.next = null;
    return newHead;
};

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。

/**
 * 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 middleNode = function(head) {
    let fast = head
    let slow = head
    while(fast && fast.next){
        fast = fast.next.next
        slow = slow.next
    }
    return slow
};