• 合并两个有序链表
  • 解答
• 删除链表中重复的元素
  • 解答
• 判断链表中是否有环
  • 解答

---

合并两个有序链表

See More

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = [] 输出：[]

示例 3：

输入：l1 = [], l2 = [0] 输出：[0]

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/merge-two-sorted-lists

解答

• 递归解法

/**
 * 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
  if (l2 == null) return l1

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

• 非递归解法

var mergeTwoLists = function (l1, l2) {
  // 借助一个辅助头节点
  let head = new ListNode(-1)
  // 定义一个辅助指针，一开始指向 head 节点
  let pre = head

  // 只要两个链表都不为null
  while (l1 != null && l2 != null) {
    if (l1.val <= l2.val) {
      // 由于一开始pre指向head，所以在pre指针指向head的时候，head的next指针也被同时修改了
      pre.next = l1
      l1 = l1.next
    } else {
      // 由于一开始pre指向head，所以在pre指针指向head的时候，head的next指针也被同时修改了
      pre.next = l2
      l2 = l2.next
    }

    // 这里pre指针被重新赋值了，移动pre指针
    pre = pre.next
  }

  // 如果循环结束还有没处理完的节点，则直接追加到后面即可
  pre.next = l1 == null ? l2 : l1

  return head.next
}

删除链表中重复的元素

存在一个按升序排列的链表，给你这个链表的头节点 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 deleteDuplicates = function (head) {
  if (head == null) return head
  let slow = head
  let fast = head

  while (fast != null) {
    if (fast.val !== slow.val) {
      slow.next = fast
      slow = slow.next
    }
    fast = fast.next
  }

  slow.next = fast
  return head
}

判断链表中是否有环

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

示例  2：

输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1 输出：false 解释：链表中没有环。

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

解答

• 原理

利用快慢双指针，快指针一次移动 2 个位置，慢指针一次移动 1 个位置，如果存在环，则在某一个时刻，快指针一定会和慢指针重合。

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  if (!head || !head.next) return false

  // 快指针指向头结点的下一个位置，因为循环的条件是：只要快慢指针没有重合就会一直执行
  let fast = head.next
  // 慢指针指向头结点
  let slow = head

  // 只要两个指针没有重合
  while (fast != slow) {
    if (fast == null || fast.next == null) return false
    fast = fast.next.next
    slow = slow.next
  }
  return false
}