链表

概述

用一组任意存储的单位来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。

链表与JS

上面的图用js表示

const list = {
  value: 5,
  next: {
    value: 1,
    next: {
      value: 9,
      next: null
    }
  }
}

练习1: 链表中环的入口节点

给一个链表，若其中包含环，请找出该链表的环的入口节点，否则，输出null。

function entryNodeOfLoop (list) {
  if (!list || !list.next) return null;

  // 判断链表中是否有环
  let p1 = list.next, 
      p2 = list.next.next;
  while (p1 !== p2) {
    if (p2 === null || p2.next === null) return null;
    p1 = p1.next;
    p2 = p2.next.next;
  }

  // 获取环的长度
  let length = 1, temp = p1;
  p1 = p1.next;
  while (temp !== p1) {
    p1 = p1.next;
    length++;
  }

  // 查询环的入口
  p1 = p2 = list;
  while (length-- > 0) {
    p1 = p1.next; 
  }

  while (p1 !== p2) {
    p1 = p1.next;
    p2 = p2.next;
  }
  return p1;
}

// 测试一下
var node1 = {
  value: 1,
  next: null
}
var node2 = {
  value: 2,
  next: null
}
var node3 = {
  value: 3,
  next: null
}
var node4 = {
  value: 4,
  next: null
}
var node5 = {
  value: 5,
  next: null
}
var node6 = {
  value: 6,
  next: null
}
var node7 = {
  value: 7,
  next: null
}
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
node7.next = node3;

entryNodeOfLoop(node1);

练习2: 链表转换为数组

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList

输入 2 -> 3 -> 4

输出 [4, 3, 2]

function transformListToArray(node) {
  if (!node || !node.next) return [];
  let array = [];
  while (node) {
    array.unshift(node.val);
    node = node.next;
  }
  return array;
}


// 测试一下
const list = {
  val: 2,
  next: {
    val: 3,
    next: {
      val: 4,
      next: null
    }
  }
}
transformListToArray(list)
// 输出 [4, 3, 2]

练习3：反转链表

输入一个链表，返回其反转后的链表。

输入 2 -> 3 -> 4

输出 4 -> 3 -> 2

function reverse(list) {
  let currentNode = null,
  head = list;
  while (list && list.next) {
    currentNode = list.next;
    list.next = currentNode.next;
    currentNode.next = head;
    head = currentNode;
  }
  return head;
}

// 测试一下
var list = {
  value: 2,
  next: {
    value: 3,
    next: {
      value: 4,
      next: null
    }
  }
}
reverse(list)

练习4: 合并链表

输入数组，转成两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调递增规则。

输入:  1 -> 2 -> 4 和 3 -> 5 -> 6
输出:  1 -> 2 -> 3 -> 4 -> 5 -> 6

function ListNode(value) {
  this.value = value;
  this.next = null;
}

// 将数组转换成链表，已把数组进行排序
function transformArrayToList(array) {
  if (!Array.isArray(array)) return false;

  // 先把数组进行排序
  array = array.sort();
  let list = new ListNode(null),
      node = list;
  
  while (array.length > 0) {
    let value = array.shift();
    node.next = new ListNode(value);
    node = node.next;
  }
  return list.next;
}

// 比较两个节点
function mergeList(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;

  let node = null;
  if (l1.value < l2.value) {
    node = l1;
    node.next = mergeList(l1.next, l2);
  } else if (l1.value > l2.value) {
    node = l2;
    node.next = mergeList(l1, l2.next);
  } else if (l1.value === l2.value) {
    node = l1;
    node.next = mergeList(l1.next, l2.next);
  }
  return node;
}

const l1 = transformArrayToList([1, 2, 4, 3]);
const l2 = transformArrayToList([3, 5, 6]);
const linkedList = mergeList(l1, l2) 

练习5: 链表倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。

解题思路：可以用快慢指针

输入 5 -> 4 -> 3 -> 2 , 2

输出 3

/*
* 获取链表中的倒数第k个节点
* @params {ListNode} list
* @params {Number} k
* @returns {Node}
*/
function findKthToTail(list, k) {
  if (!list)  return null;

  let fast = list,
      slow = list,
      i = 1;

  while (fast.next) {
    i++;
    fast = fast.next;
    if (i > k) {
      slow = slow.next;
    }
  }
  return (k <= i) && slow;
}

function ListNode(value) {
  this.value = value;
  this.next = null;
}

function transformArrayToList(array) {
  if (!Array.isArray(array)) return false;

  let list = new ListNode(null),
      node = list;
  while(array.length > 0) {
    let value = array.shift();
    node.next = new ListNode(value);
    node = node.next
  }
  return list.next;
}


let list = transformArrayToList([5, 4, 3, 2])
findKthToTail(list, 2); // { val: 3, next: {...} }
findKthToTail(list, 5); // false

练习6: 两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共结点。

// 获取链表的长度
function getLinkedListLength(list) {
  if (!list || !list.next) return false;
  let length = 1, current = list.next;
  while(current) {
    length++;
    current = current.next
  }
  return length;
}

function findFirstCommonNode(l1, l2) {
  if (!l1 || !l2) return null;
  let len1 = getLinkedListLength(l1),
     len2 = getLinkedListLength(l2);
  let diff, long, short;

  if (len1 > len2) {
    long = l1,
    short = l2,
    diff = len1 - len2;
  } else {
    long = l2,
    short = l1,
    diff = len2 - len1;
  }

  while(diff-- >0) {
    long = long.next;
  }

  while (long) {
    if (long === short) {
      return long;
    }
    long = long.next
    short = short.next
  }
  return null;
}


// 测试一下

let common = {
  val: 100,
  next: {
    val: 101, 
    next: {
      val: 102,
      next: null
    }
  }
}

let l1 = {
  val: 1,
  next: {
    val: 2,
    next: {
      val: 3,
      next: common
    }
  }
};

let l2 = {
  val: 5, 
  next: {
    val: 6, 
    next: common
  }
}

findFirstCommonNode(l1, l2); // { val: 100, next: { val: 101, next: { val: 102, next: null } } }

练习7: 删除链表的倒数第k个节点

给定一个链表，删除链表的倒数第 k 个节点，并且返回链表的头结点。

给定一个链表: 1->2->3->4->5, 和 k = 2.

当删除了倒数第二个节点后，链表变为 1-> 2 -> 3 ->5.

function removeKthFromTail(list, k) {
  if (!list) return false;
  let length = getLinkedListLength(list);

  if (length < k) return false;
  let idx = length - k;
  let result = new ListNode(null);
      result.next = list;
  let  pre = result,
      cur = pre.next;
  
  for (let i = 0; i < idx; i++) {
    pre = cur;
    cur = pre.next;
  }
  pre.next = cur.next;
  return result.next;
}

练习8: 回文链表

请判断一个链表是否为回文链表。

示例：

输入 1 -> 2 -> 1

输出 false


输入 1 -> 2 -> 2 -> 1

输出 true

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

  let fast = head, slow = head;
  let stack = [];

  while(fast.next && fast.next.next) {
    stack.push(slow.val);
    slow = slow.next;
    fast = fast.next.next;
  }

  // 奇数
  if (fast.next) {
    stack.push(slow.val);
  }

  while ((slow = slow.next)) {
    if (slow.val !== stack.pop()) {
      return false;
    }
  }
  return true;
}

练习9: 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

输入: 0 -> 1 -> 2 -> NULL, k = 4
输出: 2 -> 0 -> 1 -> NULL
解释:
向右旋转 1 步: 2 -> 0 -> 1 -> NULL
向右旋转 2 步: 1 -> 2 -> 0 -> NULL
向右旋转 3 步: 0 -> 1 -> 2 -> NULL
向右旋转 4 步: 2 -> 0 -> 1 -> NULL

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var rotateRight = function(head, k) {
  if (!head || k === 0) return head;
  let length = 1, temp = head;
  while (temp.next) {
    length++;
    temp = temp.next;
  }
  
  k = k % length;
  if (k === 0) return head;

  // 形成环
  temp.next = head;
  let result = head;
  for (let i = 0; i < length - k; i++) {
    temp = temp.next;
    result = result.next;
  }
  temp.next = null;
  return result;
};

练习10: 删除链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

🌰 1:

输入: 1->1->2
输出: 1->2

🌰 2:

输入: 1->1->2
输出: 1->2

!! 注意，现已是排序链表

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function deleteDuplicates(head) {
  let current = head;
  while (current && current.next) {
    if (current.val !== current.next.val) {
      current = current.next;
    } else {
      current.next = current.next.next;
    }
  }
  return head;
}

练习11: 移除链表元素

删除链表中等于给定值 val 的所有节点。

🌰 1:

输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
function removeElements(head, val) {
  let result = new ListNode(null);
  result.next = head;
  let current = result;
  while (current.next) {
    if (current.next.val === val) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return result.next;
}

练习12: 反转链表

反转一个单链表。

🌰 1:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList (head) {
  let prev = null;
  let current = head;
  while(current) {
    let temp = current.next;
    current.next = prev;
    prev = current;
    current = temp;
  }
  return prev;
};

练习13: 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

🌰 1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]

🌰 2:

输入：[1, 1, 1, 1, 2]
输出：[1, 2]

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function removeDuplicateNodes (head) {
  if (head === null) return head;
  let list = new ListNode(null),
      map = new Map(),
      prev = list,
      current = head;
  list.next = head;

  while (current) {
    if (map.has(current.val)) {
      prev.next = current.next;
      current = current.next;
    } else {
      map.set(current.val);
      prev = prev.next;
      current = current.next;
    }
  }
  return list.next;
}