自适应网站设计尺寸/百度开户流程

ps: 老文没什么人看重新发一遍

前言

本文基于leetcode的探索链表卡片所编写。遗憾的是, 我的卡片的进度为80%, 依然没有全部完成。我在探索卡片的时候, 免不了谷歌搜索。并且有一些题目, 我的解答可能不是最优解。敬请见谅。

关于链表

链表属于比较简单的数据结构, 在这里我在过多的赘述。值的注意的是, 本文都是基于单链表的, 双链表的设计我还没有实现。

常见的套路

关于链表的算法题目, 我自己总结了以下几种套路, 或者说常见的手段

1. 同时保有当前节点的指针, 以及当前节点的前一个节点的指针。
2. 快慢指针, fast指针的移动速度是slow指针的两倍, 如果链表成环那么fast和slow必然会相遇。
3. 虚假的链表头, 通过 new ListNode(0), 创建一个虚假的头部。获取真正链表只需返回head.next(这在需要生成一个新链表的时候很有用)。
4. 同时保有当前链表的尾部的指针, 以及头部的节点指针。
5. 善用while循环。
6. 链表的头部和尾部是链表比较特殊的节点, 需要注意区别对待

设计单链表

原题的地址, 我在原题的基础使用了TypeScript模拟实现了链表。

链表需要拥有以下几种方法:

• get, 根据链表的索引获取链表节点的value

• addAtTail, 添加一个节点到链表的尾部

• addAtHead, 添加一个节点到链表的头部

• addAtIndex, 添加一个节点到链表的任意位置

• deleteAtIndex, 删除任意位置的节点

// 定义链表节点类以及链表类的接口
interface LinkedListNodeInterface {val: number;next: LinkedListNode;
}interface LinkedListInterface {head: LinkedListNode;length: number;get(index: number): number;addAtHead(val: number): void;addAtTail(val: number): void;addAtIndex(index: number, val: number): void;deleteAtIndex(index: number): void
}class LinkedListNode implements LinkedListNodeInterface {constructor (public val: number = null,public next: LinkedListNode = null) {}
}class LinkedList implements LinkedListInterface {constructor (public head: LinkedListNode = null,public length: number = 0) {}/*** 通过while循环链表, 同时在循环的过程中使用计数器计数, 既可以实现*/public get(index: number): number {if (index >= 0 && index < this.length) {let num: number = 0let currentNode: LinkedListNode = this.headwhile (index !== num) {num += 1currentNode = currentNode.next}return currentNode.val}return -1}/*** 将新节点的next属性指向当前的head, 将head指针指向新节点*/public addAtHead (val: number): void {let newNode: LinkedListNode = new LinkedListNode(val, this.head)this.head = newNodethis.length += 1}/*** 将链表尾部的节点的next属性指向新生成的节点, 获取链表尾部的节点需要遍历链表*/public addAtTail(val: number): void {let newNode: LinkedListNode = new LinkedListNode(val, null)let currentNode: LinkedListNode = this.headif (!this.head) {this.head = newNode} else {while (currentNode && currentNode.next) {currentNode = currentNode.next}currentNode.next = newNode}this.length += 1}/*** 这里需要需要运用技巧, 遍历链表的同时, 同时保留当前的节点和当前节点的前一个节点的指针*/public addAtIndex(index: number, val: number): void {if (index >= 0 && index <= this.length) {let newNode: LinkedListNode = nullif (index === 0) {// 如果index为0, 插入头部需要与其他位置区别对待this.addAtHead(val)} else {let pointer: number = 1let prevNode: LinkedListNode = this.headlet currentNode: LinkedListNode = this.head.nextwhile (pointer !== index && currentNode) {prevNode = currentNodecurrentNode = currentNode.nextpointer += 1}// 中间插入newNode = new LinkedListNode(val, currentNode)prevNode.next = newNodethis.length += 1}}}public deleteAtIndex(index: number): void {if (index >= 0 && index < this.length && this.length > 0) {if (index === 0) {this.head = this.head.next} else {let pointer: number = 1let prevNode: LinkedListNode = this.headlet currentNode: LinkedListNode = this.head.next// 值得注意的是这里的判断条件使用的是currentNode.next// 这意味着currentNode最远到达当前链表的尾部的节点，而非null// 这是因为prevNode.next = prevNode.next.next, 我们不能取null的next属性while (pointer !== index && currentNode.next) {prevNode = currentNodecurrentNode = currentNode.nextpointer += 1}prevNode.next = prevNode.next.next}this.length -= 1}}
}
复制代码

环形链表

原题地址, 将环形链表想象成一个跑道, 运动员的速度是肥宅的两倍, 那么经过一段时间后, 运动员必然会超过肥宅一圈。这个时候, 运动员和肥宅必然会相遇。快慢指针的思想就是源于此。

/*** 判断链表是否成环*/
function hasCycle (head: LinkedListNode): boolean {// 快指针let flst = head// 慢指针let slow = headwhile (flst && flst.next && flst.next.next) {flst = flst.next.nextslow = flst.nextif (flst === slow) {return true}}return false
}
复制代码

环形链表II

原题地址, 在环形链表的基础上, 我们需要获取环形链表的入口。同样使用快慢指针实现。但是值的注意的是。链表可能只有部分成环, 这意味着。快慢指针相遇的点, 可能并不是环的入口。

慢节点的运动距离为, a + b - c

快节点的运动距离为, 2b + a - c

快节点的运动距离是慢节点的两倍。可以得出这个公式 2(a + b - c) = 2b + a - c, 化简 2a - 2c = a - c, 可以得出 a = c。

相遇的点距离入口的距离, 等于起点距离入口距离

function hasCycleEntrance (head: LinkedListNode): LinkedListNode | Boolean {// 快指针let flst = head// 慢指针let slow = headwhile (flst && flst.next && flst.next.next) {flst = flst.next.nextslow = flst.next// 快指针移动到入口，并且速度变为1if (flst === slow) {// 变道起点flst = head// a 和 c距离是一致的// 每一次移动一个next，必然会在入口出相遇while (flst !== slow) {flst = flst.nextslow = slow.next}return flst}}return false
}
复制代码

相交链表

原题地址, 相交链表的解题思路依然是使用快慢指针。思路见下图, 将a链的tail链接到b链head, 如果a与b链相交, 那么就会成环。套用上一题的思路就可以获取到a与b的交点。

function hasCross (headA: LinkedListNode, headB: LinkedListNode): LinkedListNode {if (headA && headB) {// 自身相等的情况下if (headA === headB) {return headA}// a链的tail连上b链的headlet lastA: LinkedListNode = headAlet lastB: LinkedListNode = headBwhile (lastA && lastA.next) {lastA = lastA.next}lastA.next = headBlet fast: LinkedListNode = headAlet slow: LinkedListNode = headAwhile (fast && fast.next && fast.next.next) {slow = slow.nextfast = fast.next.nextif (slow === fast) {fast = headAwhile (slow !== fast) {slow = slow.nextfast = fast.nextif (slow === fast) {lastA.next = nullreturn slow}}lastA.next = nullreturn fast} }lastA.next = null  return null  } 
}
复制代码

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

原题地址, 这里我使用的是比较笨的办法, 先计算链表的长度, 获取正序的时n的大小。然后按照删除链表中某一个节点的方法进行删除即可。需要区分删除的是否是第一个。

反转链表

原题地址, 常见的反转链表的方式就是使用递归或者迭代的方式。反转链表的过程, 如果拆解开来, 可以分为下面几步。从拆解的过程可以看出, 反转链表的过程就是依次将head的后面的节点, 放到链表的头部。

1 -> 2 -> 3 -> 4 -> null

2 -> 1 -> 3 -> 4 -> null

3 -> 2 -> 1 -> 4 -> null

4 -> 3 -> 2 -> 1 -> null

const reverseList = function(head: LinkedListNode): LinkedListNode {let newHead: LinkedListNode = headlet current: LinkedListNode = head// current的指针将会向后移动function reverse () {let a = current.nextlet b = current.next.nexta.next = headcurrent.next = bhead = a}while (current && current.next) {reverse() }return head
};
复制代码

删除链表中的节点

原题地址。我使用的也是笨办法。由于链表头部特殊性，删除头部时需要进行递归(因为在第一次删除头部的节点后, 新的头部也有可能是满足删除条件的节点)。对于其他位置的节点使用常规办法即可。

function removeElements (head: LinkedListNode, val: number): LinkedListNode {/*** 删除链表的头部*/function deleteHead () {head = head.nextif (head && head.val === val) {deleteHead()}} if (head) {if (head.val === val) {// 递归删除头部的节点deleteHead()}if (head && head.next) {let prevNode = headlet currentNode = head.nextwhile (currentNode) {// 删除链表中间符合条件的节点if (currentNode.val === val) {prevNode.next = currentNode.nextcurrentNode = currentNode.next} else {prevNode = prevNode.nextcurrentNode = currentNode.next}}}  }return head
}
复制代码

奇偶链表

原题地址, 对于这道题目我们就需要运用上之前提到的两种套路(同时保留头部的指针以及当前的节点的指针和虚假的头部)

function oddEvenList (head: LinkedListNode): LinkedListNode {let oddHead: LinkedListNode = new LinkedListNode(0)let evenHead: LinkedListNode = new LinkedListNode(0)let oddTail: LinkedListNode = oddHeadlet evenTail: LinkedListNode = evenHeadlet index: number = 1while (head) {// 链接不同奇偶两条链// 这里默认开头是1，所以index从1开始if (index % 2 !== 0) {oddTail.next = headoddTail = oddTail.next} else {evenTail.next = headevenTail = evenTail.next}head = head.nextindex += 1}// 偶数链的结尾是null，因为是尾部evenTail.next = null// evenHead.next忽略到假头oddTail.next = evenHead.next// oddHead.next忽略到假头return oddHead.next
}
复制代码

回文链表

原题地址, 何为所谓的回文链表, 1 -> 2 -> 1 或者 1 -> 1 亦或则 1 -> 2 -> 2 -> 1 可以被称为回文链表。回文链表如果长度为奇数, 那么除去中间点, 两头的链表应当是在反转后应当是相同的。如果是偶数个, 链表的一半经过反转应该等于前半部分。当然有两种情况需要特殊考虑, 比如链表为 1 或者 1 -> 1 的情况下。在排除了这两种特色情况后, 可以通过快慢指针获取链表的中点(fast的速度是slow的两倍)。反转中点之后的链表后, 然后从头部开始和中点开始对比每一个节点的val。

function isPalindrome (head: LinkedListNode): boolean {if (!head) {return true}// 通过快慢指针获取中点let fast: LinkedListNode = headlet slow: LinkedListNode = head// 链表中点let middle = null// 循环结束后慢节点就是链表的中点while (fast && fast.next && fast.next.next) {fast = fast.next.nextslow = slow.next}// 一个和两个的情况if (fast === slow) {if (!fast.next) {return true} else if ( fast.val === fast.next.val ) {return true} else {return false}}// middle保持对中点的引用// slow往后移动middle = slow// 反转中点以后的链表function reverse () {let a = slow.nextlet b = slow.next.nexta.next = middleslow.next = bmiddle = a}while (slow && slow.next) {reverse()}// 从头部和中点开始对比while (head && middle) {if (head.val !== middle.val) {return false}head = head.nextmiddle = middle.next}return true    
}
复制代码

合并两个有序链表

原题地址, 对于创建一个新的链表使用的思路就是创建一个虚假的头部, 这道题目的解答也是如此。以及同时保留头部的指针以及尾部的指针, 无论是添加节点还是返回链表都会非常方便。

function mergeTwoLists (l1: LinkedListNode, l2: LinkedListNode): LinkedListNode {// 头部的引用let newHead: LinkedListNode = new LinkedListNode(0)// 尾部的引用let newTail: LinkedListNode = newHeadwhile (l1 && l2) {if (l1.val < l2.val) {newTail.next = l1l1 = l1.next} else {newTail.next = l2l2 = l2.next}// 始终指向尾部newTail = newTail.next}if (!l1) {newTail.next = l2}if (!l2) {newTail.next = l1}// 忽略虚假的头部return newHead.next
}
复制代码

链表相加

原题地址。生成虚假的头部后, 两个链表两两相加, 注意进位以及保留位即可。如果val不存在, 取0。

(2 -> 4 -> 3) + (5 -> 6 -> 7 -> 8)

0343

• 8765

9108

function addTwoNumbers (l1: LinkedListNode, l2: LinkedListNode): LinkedListNode {let newHead: LinkedListNode = new LinkedListNode(0)let newTail: LinkedListNode = newHead// carry是进位，8 + 8 = 16 ，进位为1let carry: number = 0while (l1 || l2) {let a: number = l1 ? l1.val : 0let b: number = l2 ? l2.val : 0// val是保留的位let val: number = (a + b + carry) % 10carry = Math.floor((a + b + carry) / 10)let newNode = new LinkedListNode(val)newTail.next = newNodenewTail = newTail.nextif (l1) {l1 = l1.next}if (l2) {l2 = l2.next}}if (carry !== 0) {// 注意最后一位的进位let newNode: LinkedListNode = new LinkedListNode(carry)newTail.next = newNodenewTail = newTail.next}return newHead.next
}
复制代码

旋转链表

原题地址, 通过观察可知, 所谓的旋转就是依次将链表尾部的节点移动到链表的头部, 同时可以发现如果旋转的次数等于链表的长度。链表是没有发生改变的。所以通过提前计算出链表的长度, 可以减少旋转的次数。

输入: 0-> 1-> 2 -> NULL

向右旋转 1 步: 2 -> 0 -> 1 -> NULL 向右旋转 2 步: 1 -> 2 -> 0 -> NULL 向右旋转 3 步: 0 -> 1 -> 2 -> NULL 向右旋转 4 步: 2 -> 0 -> 1 -> NULL

var rotateRight = function(head, k) {if (!head || !head.next) {return head}let length = 0let c = head// 计算出链表的长度while (c) {length += 1c = c.next}// 将链表的尾部移动到链表的头部// 链表尾部的前一个next指向nullfunction rotate () {let a = headlet b = head.nextwhile (b && b.next) {a = bb = b.next}b.next = headhead = ba.next = null}// 避免没有必要的选装let newK = k % lengthlet index = 1while (index <= newK) {rotate()index += 1}return head
};
复制代码