leetcode 链表相关题目解析

前言本文基于leetcode的探索链表卡片所编写。遗憾的是, 我的卡片的进度为80%, 依然没有全部完成。我在探索卡片的时候, 免不了谷歌搜索。并且有一些题目, 我的解答可能不是最优解。敬请见谅。关于链表链表属于比较简单的数据结构, 在这里我在过多的赘述。值的注意的是, 本文都是基于单链表的, 双链表的设计我还没有实现。常见的套路关于链表的算法题目, 我自己总结了以下几种套路, 或者说常见的手段同时保有当前节点的指针, 以及当前节点的前一个节点的指针。快慢指针, fast指针的移动速度是slow指针的两倍, 如果链表成环那么fast和slow必然会相遇。虚假的链表头, 通过 new ListNode(0), 创建一个虚假的头部。获取真正链表只需返回head.next(这在需要生成一个新链表的时候很有用)。同时保有当前链表的尾部的指针, 以及头部的节点指针。善用while循环。链表的头部和尾部是链表比较特殊的节点, 需要注意区别对待设计单链表原题的地址, 我在原题的基础使用了TypeScript模拟实现了链表。链表需要拥有以下几种方法:get, 根据链表的索引获取链表节点的valueaddAtTail, 添加一个节点到链表的尾部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 = 0 let currentNode: LinkedListNode = this.head while (index !== num) { num += 1 currentNode = 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 = newNode this.length += 1 } /* * 将链表尾部的节点的next属性指向新生成的节点, 获取链表尾部的节点需要遍历链表 / public addAtTail(val: number): void { let newNode: LinkedListNode = new LinkedListNode(val, null) let currentNode: LinkedListNode = this.head if (!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 = null if (index === 0) { // 如果index为0, 插入头部需要与其他位置区别对待 this.addAtHead(val) } else { let pointer: number = 1 let prevNode: LinkedListNode = this.head let currentNode: LinkedListNode = this.head.next while (pointer !== index && currentNode) { prevNode = currentNode currentNode = currentNode.next pointer += 1 } // 中间插入 newNode = new LinkedListNode(val, currentNode) prevNode.next = newNode this.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 = 1 let prevNode: LinkedListNode = this.head let currentNode: LinkedListNode = this.head.next // 值得注意的是这里的判断条件使用的是currentNode.next // 这意味着currentNode最远到达当前链表的尾部的节点，而非null // 这是因为prevNode.next = prevNode.next.next, 我们不能取null的next属性 while (pointer !== index && currentNode.next) { prevNode = currentNode currentNode = currentNode.next pointer += 1 } prevNode.next = prevNode.next.next } this.length -= 1 } }}环形链表原题地址, 将环形链表想象成一个跑道, 运动员的速度是肥宅的两倍, 那么经过一段时间后, 运动员必然会超过肥宅一圈。这个时候, 运动员和肥宅必然会相遇。快慢指针的思想就是源于此。/* * 判断链表是否成环 /function hasCycle (head: LinkedListNode): boolean { // 快指针 let flst = head // 慢指针 let slow = head while (flst && flst.next && flst.next.next) { flst = flst.next.next slow = flst.next if (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 = head while (flst && flst.next && flst.next.next) { flst = flst.next.next slow = flst.next // 快指针移动到入口，并且速度变为1 if (flst === slow) { // 变道起点 flst = head // a 和 c距离是一致的 // 每一次移动一个next，必然会在入口出相遇 while (flst !== slow) { flst = flst.next slow = 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链的head let lastA: LinkedListNode = headA let lastB: LinkedListNode = headB while (lastA && lastA.next) { lastA = lastA.next } lastA.next = headB let fast: LinkedListNode = headA let slow: LinkedListNode = headA while (fast && fast.next && fast.next.next) { slow = slow.next fast = fast.next.next if (slow === fast) { fast = headA while (slow !== fast) { slow = slow.next fast = fast.next if (slow === fast) { lastA.next = null return slow } } lastA.next = null return fast } } lastA.next = null return null } }删除链表的倒数第N个节点原题地址, 这里我使用的是比较笨的办法, 先计算链表的长度, 获取正序的时n的大小。然后按照删除链表中某一个节点的方法进行删除即可。需要区分删除的是否是第一个。反转链表原题地址, 常见的反转链表的方式就是使用递归或者迭代的方式。反转链表的过程, 如果拆解开来, 可以分为下面几步。从拆解的过程可以看出, 反转链表的过程就是依次将head的后面的节点, 放到链表的头部。1 -> 2 -> 3 -> 4 -> null2 -> 1 -> 3 -> 4 -> null3 -> 2 -> 1 -> 4 -> null4 -> 3 -> 2 -> 1 -> nullconst reverseList = function(head: LinkedListNode): LinkedListNode { let newHead: LinkedListNode = head let current: LinkedListNode = head // current的指针将会向后移动 function reverse () { let a = current.next let b = current.next.next a.next = head current.next = b head = a } while (current && current.next) { reverse() } return head};删除链表中的节点原题地址。我使用的也是笨办法。由于链表头部特殊性，删除头部时需要进行递归(因为在第一次删除头部的节点后, 新的头部也有可能是满足删除条件的节点)。对于其他位置的节点使用常规办法即可。function removeElements (head: LinkedListNode, val: number): LinkedListNode { /* * 删除链表的头部 */ function deleteHead () { head = head.next if (head && head.val === val) { deleteHead() } } if (head) { if (head.val === val) { // 递归删除头部的节点 deleteHead() } if (head && head.next) { let prevNode = head let currentNode = head.next while (currentNode) { // 删除链表中间符合条件的节点 if (currentNode.val === val) { prevNode.next = currentNode.next currentNode = currentNode.next } else { prevNode = prevNode.next currentNode = currentNode.next } } } } return head}奇偶链表原题地址, 对于这道题目我们就需要运用上之前提到的两种套路(同时保留头部的指针以及当前的节点的指针和虚假的头部)function oddEvenList (head: LinkedListNode): LinkedListNode { let oddHead: LinkedListNode = new LinkedListNode(0) let evenHead: LinkedListNode = new LinkedListNode(0) let oddTail: LinkedListNode = oddHead let evenTail: LinkedListNode = evenHead let index: number = 1 while (head) { // 链接不同奇偶两条链 // 这里默认开头是1，所以index从1开始 if (index % 2 !== 0) { oddTail.next = head oddTail = oddTail.next } else { evenTail.next = head evenTail = evenTail.next } head = head.next index += 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 = head let slow: LinkedListNode = head // 链表中点 let middle = null // 循环结束后慢节点就是链表的中点 while (fast && fast.next && fast.next.next) { fast = fast.next.next slow = 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.next let b = slow.next.next a.next = middle slow.next = b middle = a } while (slow && slow.next) { reverse() } // 从头部和中点开始对比 while (head && middle) { if (head.val !== middle.val) { return false } head = head.next middle = middle.next } return true }合并两个有序链表原题地址, 对于创建一个新的链表使用的思路就是创建一个虚假的头部, 这道题目的解答也是如此。以及同时保留头部的指针以及尾部的指针, 无论是添加节点还是返回链表都会非常方便。function mergeTwoLists (l1: LinkedListNode, l2: LinkedListNode): LinkedListNode { // 头部的引用 let newHead: LinkedListNode = new LinkedListNode(0) // 尾部的引用 let newTail: LinkedListNode = newHead while (l1 && l2) { if (l1.val < l2.val) { newTail.next = l1 l1 = l1.next } else { newTail.next = l2 l2 = 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)03438765__ 9108function addTwoNumbers (l1: LinkedListNode, l2: LinkedListNode): LinkedListNode { let newHead: LinkedListNode = new LinkedListNode(0) let newTail: LinkedListNode = newHead // carry是进位，8 + 8 = 16 ，进位为1 let carry: number = 0 while (l1 || l2) { let a: number = l1 ? l1.val : 0 let b: number = l2 ? l2.val : 0 // val是保留的位 let val: number = (a + b + carry) % 10 carry = Math.floor((a + b + carry) / 10) let newNode = new LinkedListNode(val) newTail.next = newNode newTail = newTail.next if (l1) { l1 = l1.next } if (l2) { l2 = l2.next } } if (carry !== 0) { // 注意最后一位的进位 let newNode: LinkedListNode = new LinkedListNode(carry) newTail.next = newNode newTail = 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 -> NULLvar rotateRight = function(head, k) { if (!head || !head.next) { return head } let length = 0 let c = head // 计算出链表的长度 while (c) { length += 1 c = c.next } // 将链表的尾部移动到链表的头部 // 链表尾部的前一个next指向null function rotate () { let a = head let b = head.next while (b && b.next) { a = b b = b.next } b.next = head head = b a.next = null } // 避免没有必要的选装 let newK = k % length let index = 1 while (index <= newK) { rotate() index += 1 } return head};