链表

特性

• 数组需要申请连续的内存空间，链表可以使用“零散的”内存空间
• 头尾操作时间复杂度O(1)
• 随机访问时间复杂度O(n)

结构

• 零散的内存块称为结点
• 记录下一个结点地址的指针叫做后继指针next
• headNode
• tailNode.next = null

种类

• 单链表

• 循环链表

  tailNode.next = headNode

  适合处理环状结构的数据

• 双向链表

  结点拥有两个指针
  curNode.prev
curNode.next

  O(1)时间复杂度即可访问前序结点

• 双向循环链表

  headNode.prev = tailNode
tailNode.next = headNode

实现

// 单向链表
class Node {
	constructor(value) {
		this.value = value;
		this.next = null;
	}
}
class linkedList {
	constructor(value) {
		this.head = new Node(value);
		this.length = 0;
		this.tail = this.head;
	}
	// 尾部追加
	append(value) {
		const _newNode = new Node(value);
		this.tail.next = _newNode;
		this.tail = _newNode;
		this.length++;
		// 返回链表
		return this;
	}

	// 头部添加
	prepend(value) {
		const _newNode = new Node(value);
		_newNode.next = this.head;
		this.head = _newNode;
		// 返回链表
		return this;
	}

	// 查找
	search(value) {
		let cur = this.head;
		while (cur) {
			if (cur.value === value) {
				return true;
			}
			cur = cur.next;
		}
		return false;
	}

  traverseTiIndex(index){
    let _index = 0
    let current = this.head
    while(_index < index){
      current = current.next
      _index++
    }
    return current
  }
	// position插入
	insert(position, value) {
		if (position === 0) return this.prepend(value);
		if (position >= this.length) return this.append(value);
    // 访问到该位置前一个节点
    const _pre = this.traverseToIndex(position - 1)
    // 被插入的位置
    const _next = pre.next
    const _newNode = new Node(value)
    _pre.next = _newNode
    _newNode.next = _next
    this.length ++ 
    return this
	}
	// position删除
	remove(position) {
    if(position>=this.length) return false

    const _pre = this.traverseToIndex(position - 1)
    const _next = _pre.next.next
    _pre.next = _next
    this.length --
    return this
	}
}

// 双向链表
class Node {
	constructor(value) {
		this.value = value;
		this.previous = null;
		this.next = null;
	}
}

class DoubleLinkedList {
	constructor(value) {
		this.head = new Node(value);
		this.tail = this.head;
		this.length = 1;
	}

	append(value) {
		const n = new Node(value);
		const preTail = this.tail;
		preTail.next = n;
		n.previous = preTail;
		this.tail = n;
		this.length++;
		return this;
	}

	prepend(value) {
		const n = new Node(value);
		const preHead = this.head;
		preHead.previous = n;
		n.next = preHead;
		this.head = n;
		this.length++;
		return this;
	}

	traverseToIndex(position) {
		let index = 0;
		let current = this.head;
		while (index < position) {
			current = current.next;
			index++;
		}
		return current;
	}

	insert(position, value) {
		if (position >= this.length) return this.append(value);
		if (position <= 0) return this.prepend(value);
		const preNode = this.traverseToIndex(position - 1);
		const n = new Node(value);
		const nextNode = preNode.next;
		preNode.next = n;
		n.previous = preNode;
		n.next = nextNode;
		nextNode.previous = n;
		this.length++;
		return this;
	}

	remove(position) {
		if (position < 0 || position >= this.length) return false;
		if (position < 1) {
			const newHead = this.head.next;
			newHead.previous = null;
			this.head = newHead;
		} else {
			const preNode = this.traverseToIndex(position - 1);
			const targetNode = preNode.next.next;
			preNode.next = targetNode;
			targetNode.previous = preNode;
		}
		this.length--;
		return this;
	}
}

题目

注意边界情况

• 链表为空
• 链表只有一个结点
• 链表只有两个结点
• 处理头部结点和尾部结点

练习

• 单链表反转

function reverseLinkedList(head) {
	// 长度为1
	if (!head.next) return head;
	// 链表反过来，则head的值为null
	let pre = null;
	let cur = head;
	// 链表正向走完后.next = null
	while (cur) {
		const _next = cur.next;
		cur.next = pre;
		pre = cur;
		cur = _next;
	}
	return pre;
}

// es6？？
let [pre, cur] = [null, head];
while (cur) {
	[cur.next, pre, cur] = [pre, cur, cur.next];
}
return pre;

• 检测链表是否循环

//
JSON.stringify(); //不能序列化循环链表

//标记
function isLoop(head) {
	if (!head) return false;
	let cur = head;
	while (cur) {
		if (cur.flag) return true;
		cur.flag = true;
		cur = cur.next;
	}
	return false;
}

// 快慢指针
function isLoop2(head) {
	if (!head || !head.next) return false;
	let fast = head.next.next;
	let slow = head.next;
	while (slow !== fast) {
		if (!fast || !fast.next) {
			return false;
		}
		fast = fast.next.next;
		slow = slow.next;
	}
	return true;
}

• 实现 LRU 缓存淘汰策略

function Node(value) {
	this.value = value;
	this.next = null;
}
function LRULinkedList(maxSize) {
	this.maxSize = maxSize;
	this.head = null;
	this.curSize = 0;

	this.visit = (value) => {
		const n = new Node(value);
		let cur = this.head,
			pre = this.head;
		let preCatch, curCatch;
		if (!cur) {
			this.head = n;
			this.curSize = 1;
			return;
		}
		if (cur.value === value) return;
		while (cur) {
			if (cur.value === value) {
				// 找到了
				// 从原来位置删除并作为头
				pre.next = cur.next;
				cur.next = this.head;
				return;
			}
			preCatch = pre;
			curCatch = cur;
			pre = cur;
			cur = cur.next;
		}
		// 没找到
		if (this.curSize < maxSize) {
			// 插入头部
			n.next = this.head;
			this.head = n;
			this.curSize++;
		} else {
			// 删除尾部结点
			// 插入头部
			preCatch.next = null;
			curCatch.next = this.head;
			this.head = curCatch;
		}
	};
}

• 回文链表

// 快慢指针找出中点
// 一半的链表与另一半链表组成的栈对比
function isPalindrome(head) {
	if (!head || !head.next) return true;
	const stack = [];
	let slow = head;
	let fast = head;
	while (fast && fast.next && fast.next.next) {
		slow = slow.next;
		fast = fast.next.next;
	}
	let mid = slow;
	while (mid.next) {
		stack.push(mid.next);
		mid = mid.next;
	}
	while (stack.length > 0) {
		if (head.value !== stack.pop().value) return false;
		head = head.next;
	}
	return true;
}
// 或者将链表转数组，对撞指针

// 另一种是到到中点后反转链表，不使用辅助栈

• 合并两个有序链表

function Node(value) {
	this.value = value;
	this.next = null;
}
// 1->2->4,1->3->4
// 1->1->2->3->4->4
function mergeLinkedList(l1, l2) {
	if (l1 === null) {
		return l2;
	}
	if (l2 === null) {
		return l1;
	}
	if (l1.value <= l2.value) {
		l1.next = mergeLinkedList(l1.next, l2);
		return l1;
	} else {
		l2.next = mergeLinkedList(l2.next, l1);
		return l2;
	}
}

// 或者蠢办法
var mergeTwoLists = function (l1, l2) {
	const n = new ListNode(-1);
	let cur = n;
	while (l1 && l2) {
		if (l1.value <= l2.value) {
			cur.next = l1;
			l1 = l1.next;
		} else {
			cur.next = l2;
			l2 = l2.next;
		}
		cur = cur.next;
	}
	// 有一条到头咯
	if (l1) {
		cur.next = l1;
	} else {
		cur.next = l2;
	}
	return n.next;
};

• 查找两个链表的公共起始点

function commonPrefix(headA, headB) {
	if (!headA || !headB) return null;
	while (headA) {
		headA.flag = true;
		headA = headA.next;
	}
	while (headB) {
		if (headB.flag) return headB;
		headB.flag = true;
		headB = headB.next;
	}
	return null;
}

function commonPrefix2(headA, headB) {
	if (!headA || !headB) return null;
	// 连个链表同时移动指针
	let n1 = headA;
	let n2 = headB;
	while (n1 || n2) {
		if (n1 === n2) return n1;
		//指针到头后跳到对面的开头
		n1 = n1 === null ? headB : n1.next;
		n2 = n2 === null ? headA : n2.next;
	}
	return null;
}

• 删除特定值链表节点

function deleteNode(head, value) {
	if (!head) return;
	if (head.value === value) {
		return head.next;
	}
	head.next = deleteNode(head.next, value);
	return head;
}

• 返回链表中特定位置节点

// 计数法
// 一遍算链表长度
// 一遍根据位置.next

// 计数法配合map
function getKthFromEnd(head, k) {
	let pos = 1;
	const map = new Map();
	while (head) {
		map.set(pos++, head);
		head = head.next;
	}
	return map.get(pos - k);
}

// 双指针
// 返回倒数k位置
//  * Definition for singly-linked list.
//  * function ListNode(value) {
//  *     this.value = value;
//  *     this.next = null;
//  * }
function getKthFromEnd(head, k) {
	let fast = head;
	let slow = head;
	let t = 0;
	while (fast.next) {
		fast = fast.next;
		t++;
		if (t >= k) slow = slow.next;
	}
	return slow;
}

• 字符串中第一个不重复字符

//map
function firstUniqChar(s){
  if(!s) return ' '
  const map = new Map()
  for(let [i,v] of Array.from(s).entries()){
    if(map.has(v)){
			return v
    }else{
      map.set(v,i)
    }
  }
  return ' '
}
//
...
indexOf===lastIndexOf
...

• 字符串能否构成回文

字符顺序修改后能否回文
相当于非回文字符最多只有一个

function canPermutePalindrome(s) {
	// map // object都行
}
var canPermutePalindrome = function (s) {
	const obj = {};
	for (let i = 0; i < s.length; i++) {
		const str = s[i];

		if (obj[str]) {

			delete obj[str];
		} else {
			// 使用object时，上面的if(obj[str])会和这里冲突
			// 刚好设置obj[str] = 0
			// if判断不成立
			obj[str] = 1;
		}
	}
	return Object.keys(obj).length <= 1;
};