数据结构 - 3.链表 - 《数据结构与算法》

1.什么是链表(ListNode)
2.链表的优点
3.链表的方法
例题

1.什么是链表(ListNode)

非连续空间的存储结构
每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（有些语言称为指针或者连接）组成

2.链表的优点

内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理
链表不必在创建时就确定大小，并且大小可以无限的延伸下去
链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多

3.链表的方法

链表常见操作：
通用
isEmpty()
size()
toString()
增：
append(element)
insert(position, element)
删:
removeAt(position)
remove(element)
查：
get(position)
indexOf(element)
改:
update(po)

1.创建链表，添加节点

function LinkedList() {
  // 内部的类：节点类
  function Node(data) {
    this.data = data
    this.next = null
  }
  // 链表的第一个
  this.head = null
  // 链表长度
  this.length = 0
  // 1.append
  // 添加操作其实是将最后一个 node 的 next 指向新节点
  LinkedList.prototype.append = function(data) {
    // 1.1 创建新节点
    let newNode = new Node(data)
    // 1.2 判断是否添加的是第一个节点
    if (this.length === 0) { // 是第一个节点
      this.head = newNode
    } else {
      let current = this.head
      // 1.3 找到最后的一个节点，并将 next 指向新节点
      while(current.next) {
        current = current.next
      }
      current.next = newNode
    }
    this.length += 1
  }
}

2.toString 方法

拿到 node 节点的每一项的值，拼接起来返回字符串

// 2.toString 方法
LinkedList.prototype.toString = function() {
    // 2.1 定义变量
    let current = this.head
    let listString = ""
    // 2.2 循环获取一个个节点
    while(current) {
        listString += current.data + ' '
        current = current.next
    }
    return listString.slice(1)
}

3.insert(position, element) 方法

找到链表中 position 的位置，将前一项的 next 指向new Node，将newNode的next指向下一项

// 3.insert方法
LinkedList.prototype.insert = function(position, data) {
  // 3.1 对 position 进行越界判断
  if (position < 0 || position > this.length) return false
  // 3.2 根据 data 创建 newNode
  let newNode = new Node(data)
  // 3.3 判断插入的位置是否是第一个
  if (position === 0) {
    newNode.next = this.head
    this.head = newNode
  } else {
    let current = this.head
    let previous = null
    // 如果当前项小于插入的 position
    for(let i=0; i<position; i++) {
      previous = current
      current = current.next
    }
    newNode.next = current
    previous.next = newNode
  }
  this.length += 1
  return true
}

4.get(position)方法

获取某个positon上的node data

LinkedList.prototype.get = function(position) {
    // 1.越界判断
    if (position < 0 || position >= this.length) return null
    // 2.获取对应的 data
    let current = this.head
    let index = 0
    while(index < position) {
        current = current.next
        index++
    }
    return current.data
}

5.indexOf(element)

获取元素值的 index

LinkedList.prototype.indexOf = function (element) {
    let index = 0
    let current = this.head
    while(index < this.length) {
        if (current.data === element) {
            return index
        }
        index++
        current = current.next
    }
    // 找不到 return -1
    return -1
};

6.update(position, data)

找到position位置的节点，更新 data

LinkedList.prototype.update = function(position, newData) {
  // 越界判断
  if (position < 0 || position >= this.length) {
    return false
  }
  // 查找正确的节点
  let current = this.head
  let index = 0
  while(index++ < position) {
    current = current.next
  }
  // 将 position 位置的 node 的 data 修改成 newData
  current.data = newData
}

7.removeAt(position)

删除index上的元素，其实是将上一项的next直接指向后一项

LinkedList.prototype.removeAt = function(position) {
  // 1.越界判断
  if (position < 0 || position >= this.length) return false

  // 2.判断是否删除的是第一个节点
  let current = this.head
  if (position === 0) {
    this.head = this.head.next
  } else {
    let index = 0
    let prev = null
    while(index < position) {
      prev = current
      current = current.next
      index++
    }
    // 跳过当前current，将前一项的next指向current.next
    prev.next = current.next
  }
  this.length -= 1
  return current.data
}

8.remove(data)

删除链表上的某个元素，其实就是将上一项的next指向后一项, length-1

LinkedList.prototype.remove = function (data) {
  // // 1.获取 data 在链表中的位置信息
  // let position = this.indexOf(data)
  // // 2.根据 position 调用 removeAt
  // return this.removeAt(position)

  // 找到 data 在链表的位置
  // 如果存在，就将前一个node next指向后一位
  let index = 0;
  let current = this.head;
  let previous = null;
  while (index < this.length) {
    // 找到该元素
    if (current.data === data) {
      if (index === 0) {
        this.head = current.next;
        return current
      } else {
        previous.next = current.next;
        return current
      }
      this.length -= 1
    } else {
      previous = current;
      current = current.next;
      index++;
    }
  }
};

例题

1.反转链表

方法1：反向遍历

遍历链表，放到一个队列中

反向遍历队列，修改每一个node的next为前一项，第length-1项的next为null

var reverseList = function (head) {
if (!head) return null
let queue = [];
while (head) {
 queue.push(head);
 head = head.next;
}
for (let i = queue.length - 1; i >= 0; i--) {
 if (i !== 0) {
   queue[i].next = queue[i - 1];
 } else {
   queue[0].next = null;
 }
}
return queue[queue.length - 1]
};

方法2：摘除法，每次摘掉老链表head的头部，将头部作为新链表的头部

var reverseList = function (head) {
let newNode = null
while(head) {
 let temp = head.next // head 的next后部分
 head.next = newNode // 摘除，将head的next指向新链表
 newNode = head // newNode 这时候从 head 开始了
 head = temp // 将 temp，也就是原本的head.next 变成新的 node head，直到没有
}
return newNode
};

2.两数相加

思路：

遍历两个链表，用两个指针记录链表当前位置，l3记录新链表位置

用加法运算迭代生成新的链表节点

/**
* 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) {
const l3 = new ListNode(0);
let p1 = l1; // l1 指针
let p2 = l2; // l2 指针
let p3 = l3;
let carry = 0;
while (p1 || p2) {
 let v1 = p1 ? p1.val : 0;
 let v2 = p2 ? p2.val : 0;
 let val = v1 + v2 + carry;
 p3.next = new ListNode(val % 10);
 carry = Math.floor(val / 10);
 // 移动指针到后一位
 if (p1) p1 = p1.next;
 if (p2) p2 = p2.next;
 p3 = p3.next;
}
if (carry) {
 p3.next = new ListNode(carry)
}
return l3.next;
};

3.链表去重

leetcode83.删除排序链表中的重复元素
无序链表：

遍历链表，通过 map 记录链表值

生成一个新的链表

function (head) {
let newNode = new ListNode(); // 创建一个新链表
let p1 = newNode // 新链表的指针
let p2 = head // 旧链表的指针
let map = new Map();
// 遍历旧链表
while (p2) {
if (!map.get(p2.val)) {
  map.set(p2.val, true);
  // 如果说新链表没有包含该 node，则生成
  p1.next = new ListNode(p2.val)
  p1 = p1.next // 指针向后移动
  p2 = p2.next
} else {
  // 如果包含，则直接移动p2指针
  p2 = p2.next
}
}
return newNode.next
};

有序链表：
如果当前项的value和next项的value相等，则将当前项的next指向current.next.next

var deleteDuplicates = function (head) {
let p1 = head // 指针
while(p1 && p1.next) { // 最后一项无序进入
if (p1.val === p1.next.val) {
  p1.next = p1.next.next
} else {
  // 防止 [1, 1, 1] 三次重复
  p1 = p1.next
}
}
return head
};

4.判断环形链表

方法：快慢指针，如果存在有环，快的指针一定会追上慢的指针

var hasCycle = function (head) {
let p1 = head
let p2 = head
while(p1 && p2 && p2.next) {
p1 = p1.next
p2 = p2.next.next
if (p1 === p2) {
  return true
}
}
return false
};

5.删除链表的倒数第N个节点

地址

方法1：

先遍历链表，记录链表的长度，再次遍历链表，当node为n的前一项时，指向当前node.next

注意删除首部和末尾需要额外处理

var removeNthFromEnd = function (head, n) {
if (n < 0) return false;
// 先获取链表的长度
let p = head;
let length = 0;
while (p) {
 length++;
 p = p.next;
}

// 删除倒数第 n 项，其实就是删除正数index 为 length - n 项
// 删除正数 length -n 就是将 length - n -1 的 next 指向 length - n 的next
let index = 0;
// 如果是第一位
if (n === length) {
 head = head.next;
 return head;
}
p = head
while (p) {
 if (index === length - n - 1) {
   // 如果是最后一位
   if (p.next) {
     p.next = p.next.next;
   } else {
     p.next = null;
   }
   return head;
 }
 index++;
 p = p.next;
}
// console.log(length);
};

方法2：快慢指针法

设置 fast指针前进 n 位

fast 和 slow同时前进，直到 fast到末尾，这个时候 slow 正好指向倒数 n+1位，因为差n位就到末尾了

function (head, n) {
let slow = head;
let fast = head;
for (let i = 0; i < n; i++) {
 fast = fast.next;
}
if (!fast) {
 // 说明删除的是第一位元素
 return head.next;
}
while (fast.next) {
 fast = fast.next;
 slow = slow.next;
}
// 此时 slow 为倒数 n + 1项
slow.next = slow.next.next;
return head;
};

6.合并两个升序链表

合并两个有序链表
思路：双指针对比两个链表，如果p1更小，则以v1为值创建新node，兵器p1=p1.next，进入下一个循环

var mergeTwoLists = function (list1, list2) {
// 合并两个升序链表
let p1 = list1
let p2 = list2
let l3 = new ListNode()
let p3 = l3
// 双指针比对val，生成新链表node
while(p1 && p2) {
 if (p1.val < p2.val) {
   p3.next = new ListNode(p1.val)
   p1 = p1.next // 比对后向后移动
 } else {
   p3.next = new ListNode(p2.val)
   p2 = p2.next
 }
 p3 = p3.next
}
// 如果有一个到尽头了，则直接将p3的next 指向没遍历完的
p1 ? p3.next = p1 : p3.next = p2
return l3.next
};