链表算法题

1.反转链表【L206】

解决办法：

1. 迭代法

/**
 * 反转箭头指向
 * 1->2->3->null
 * null<-1<-2<-3
 */
var reverseList = function(head) {
  let cur = head; // 当前节点
  let prev = null; // 当前节点的前一个节点
  // 一次循环是把当前的节点的next指向prev 周而复始
  // 千万不要想着 一次循环是两个节点位置的互换
  // 按照这个去理解null<-1<-2<-3
  while (cur) {
    let nextTemp = cur.next; // 保留剩余未反转的链表
    cur.next = prev; // 当前节点的next指向prev，反转链表
    prev = cur; // 接收反转结果
    cur = nextTemp; // 将当前指针指向剩余未反转的链表，接回临时存储的后续内容
  }
  return prev;
};

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)。

2. 递归

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

时间复杂度：O(n)，其中 nn 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 nn 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 nn 层。

2.合并两个有序链表【L21】

1. 递归

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

3.环形链表【L141】

解决办法：

1. 快慢指针

var hasCycle = function(head) {
  //设置快慢指针
  let slow = head;
  let fast = head;
  //如果没有环，则快指针会抵达终点，否则继续移动双指针
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    //快慢指针相遇，说明含有环
    if (slow == fast) {
      return true;
    }
  }
  return false;
};

2. 借助哈希表 Map

哈希表存遍历过的节点，每遍历一个节点，都查看哈希表是否存在当前节点，如果存在，则说明链表有环，如果不存在，则存入哈希表，继续遍历

时间复杂度为 O(n)，空间复杂度为 O(n)

var hasCycle = (head) => {
  let map = new Map();
  while (head) {
    if (map.has(head)) return true; //如果当前节点在map中存在就说明有环
    map.set(head, true); //否则就加入map
    head = head.next; //迭代节点
  }
  return false; //循环完成发现没有重复节点，说明没环
};

非正常解法：

1. 污链表法：为每次遍历的节点设定一个标记，如果存在环，那么一定存在某个节点已经设定过标记。否则链表遍历结束其不为环

const hasCycle = function(head) {
  while (head) {
    if (head.tag) {
      return true;
    }
    head.tag = true;
    head = head.next;
  }
  return false;
};

2. JSON.stringify 除非不报错，报错就是有环！！

var hasCycle = function(head) {
  try {
    JSON.stringify(head);
  } catch {
    return true;
  }
  return false;
};

4.删除链表的倒数第 N 个结点【L19】

1. 双指针-快慢指针

解法：如果要删除倒数第 n 个节点，让 fast 移动 n 步，然后让 fast 和 slow 同时移动，直到 fast 指向链表末尾。删掉 slow 所指向的节点就可以了。

var removeNthFromEnd = function(head, n) {
  let fast, slow;
  fast = slow = head;
  // 快指针先前进 n 步
  while (n-- > 0) {
    fast = fast.next;
  }
  if (fast == null) {
    // 如果此时快指针走到头了，
    // 说明倒数第 n 个节点就是第一个节点
    return head.next;
  }
  // 让慢指针和快指针同步向前
  while (fast != null && fast.next != null) {
    fast = fast.next;
    slow = slow.next;
  }
  // slow.next 就是倒数第 n 个节点，删除它
  slow.next = slow.next.next;
  return head;
};

5.删除排序链表中的重复元素【L83】

1. 迭代法

时间复杂度：O(n)，其中 nn 是链表的长度。

空间复杂度：O(1)。

var deleteDuplicates = function(head) {
  if (!head) {
    return head;
  }

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

6.合并 K 个升序链表【L23】

1. 递归 + 分治

时间复杂度：O(nlogK)，k 为链表总数，n 为合并两个链表所用时间

空间复杂度：O(n)

var mergeKLists = function(lists) {
  let n = lists.length;
  if (n == 0) return null;
  let mergeTwoLists = (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(l1, l2.next);
      return l2;
    }
  };
  let merge = (left, right) => {
    if (left == right) return lists[left];
    let mid = (left + right) >> 1;
    let l1 = merge(left, mid);
    let l2 = merge(mid + 1, right);
    return mergeTwoLists(l1, l2);
  };
  return merge(0, n - 1);
};

2. 合并数组，排序，转链表

思路：

（1）遍历所有链表元素，将元素值放到一个数组中

（2）排序数组，相当于按优先级排序优先级队列

（3）遍历排好序的数组，重新构造一个新的有序链表即为所求

时间复杂度：O(NlogN)，N：节点总数，O(N)：遍历开销，O(NlogN)：排序(假设稳定)，O(N)：创建新的有序链表

空间复杂度：O(N)，O(N)：创建新的有序链表

/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
  if (!lists || lists.length == 0) return null;
  let arr = [];
  let res = new ListNode(0);
  lists.forEach((list) => {
    let cur = list;
    while (cur) {
      arr.push(cur.val);
      cur = cur.next;
    }
  });
  let cur = res;
  arr
    .sort((a, b) => a - b)
    .forEach((val) => {
      let node = new ListNode(val);
      cur.next = node;
      cur = cur.next;
    });
  return res.next;
};

7.回文链表【L234】

1. 将值复制到数组中后用双指针法

时间复杂度：O(n)，其中 n 指的是链表的元素个数。

第一步： 遍历链表并将值复制到数组中，O(n)。

第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。

总的时间复杂度：O(2n) = O(n)。

空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

var isPalindrome = function(head) {
  const vals = [];
  while (head !== null) {
    vals.push(head.val);
    head = head.next;
  }
  for (let i = 0, j = vals.length - 1; i < j; ++i, --j) {
    if (vals[i] !== vals[j]) {
      return false;
    }
  }
  return true;
};

2. 快慢指针

时间复杂度：O(n)，其中 nn 指的是链表的大小。

空间复杂度：O(1)。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。

const reverseList = (head) => {
  let prev = null;
  let curr = head;
  while (curr !== null) {
    let nextTemp = curr.next;
    curr.next = prev;
    prev = curr;
    curr = nextTemp;
  }
  return prev;
};

const endOfFirstHalf = (head) => {
  let fast = head;
  let slow = head;
  while (fast.next !== null && fast.next.next !== null) {
    fast = fast.next.next;
    slow = slow.next;
  }
  return slow;
};

var isPalindrome = function(head) {
  if (head == null) return true;

  // 找到前半部分链表的尾节点并反转后半部分链表
  const firstHalfEnd = endOfFirstHalf(head);
  const secondHalfStart = reverseList(firstHalfEnd.next);

  // 判断是否回文
  let p1 = head;
  let p2 = secondHalfStart;
  let result = true;
  while (result && p2 != null) {
    if (p1.val != p2.val) result = false;
    p1 = p1.next;
    p2 = p2.next;
  }

  // 还原链表并返回结果
  firstHalfEnd.next = reverseList(secondHalfStart);
  return result;
};