这是第三周的练习题，原本应该先发第二周的，因为周末的时候，我的母亲大人来看望她的宝贝儿子，哈哈，我得带她看看厦门这座美丽的城市呀。
这两天我抓紧整理下第二周的题目和答案，下面我把之前的也列出来：
欢迎关注我
- 个人主页(https://github.com/pingan8787)
- 个人博客(http://www.pingan8787.com/)
- 个人知识库(http://js.pingan8787.com/)
- 微信公众号“前端自习课”
本周练习内容：数据结构与算法 —— LinkedList
这些都是数据结构与算法，一部分方法是团队其他成员实现的，一部分我自己做的，有什么其他实现方法或错误，欢迎各位大佬指点，感谢。
一、链表是什么？与数组有什么区别？生活中有什么案例？
解析：
概念参考阅读 [链表 —— 维基百科] (https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8)
1.概念：
链表（Linked list）是一种上一个元素的引用指向下一个元素的存储结构，链表通过指针来连接元素与元素；
链表是线性表的一种，所谓的线性表包含顺序线性表和链表，顺序线性表是用数组实现的，在内存中有顺序排列，通过改变数组大小实现。而链表不是用顺序实现的，用指针实现，在内存中不连续。意思就是说，链表就是将一系列不连续的内存联系起来，将那种碎片内存进行合理的利用，解决空间的问题。
所以，链表允许插入和删除表上任意位置上的节点，但是不允许随即存取。链表有很多种不同的类型：单向链表、双向链表及循环链表。
2.与数组的区别：
- 相同：
两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。
- 不同：
链表是链式的存储结构；数组是顺序的存储结构。
链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。
链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难。
数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。
数组和链表一些操作的时间复杂度对比：
数组：
- 查找复杂度：O(1)
- 添加/删除复杂度：O(n)
链表：
- 查找复杂度：O(n)
- 添加/删除复杂度：O(1)
3.生活中的案例：
火车，是由一些列车厢连接起来；
寻宝游戏，每个线索都是下一个线索地点的指针。
二、请实现一个链表，并实现以下方法
-
append(element)：向列表尾部添加一个新的元素。 -
insert(position,element)：向列表指定位置插入一个新的元素。 -
remove(element)：从列表中移除并返回特定元素（若有多个相同元素则取第一次出现的情况）。 -
indexOf(element)：返回元素在列表的索引（若有多个相同元素则取第一次出现的情况），如果列表中没有该元素则返回 -1。 -
removeAt(position)：从列表中，移除并返回特定位置的一项。 -
isEmpty()：如果列表不含任何元素，返回 true，否则返回 false。 -
size()：返回列表中元素个数，与数组的 length 属性类似。 -
toString()：由于列表项使用 Node 类，需要重写继承自 JavaScript 对象默认的 toString() 方法，让其只输出元素的值。
提示：Web 端优先使用 ES6 以上的语法实现。
解析：
1. class Node {
2. constructor(element){
3. this.element = element
4. this.next = null
5. }
6. }
7. class LinkedList {
8. constructor(){
9. this.length = 0
10. this.head = null
11. }
12. /**
13. * 添加元素（末尾添加）
14. * @param {*} element 添加的元素
15. */
16. append(element){
17. let node = new Node(element)
18. if(!this.head){
19. this.head = node
20. }else{
21. let current = this.head
22. // 查找最后一项
23. while(current.next){
24. current = current.next
25. }
26. // 将最后一下的next赋值为node，实现追加元素
27. current.next = node
28. }
29. this.length ++
30. }
31. /**
32. * 添加元素（指定位置）
33. * @param {Number} position 添加的位置
34. * @param {*} element 添加的元素
35. */
36. insert(position, element){
37. if(position >= 0 && position <= this.length){
38. let node = new Node(element),
39. index = 0,
40. previous = null
41. if(position === 0){
42. node.next = this.head
43. this.head = node
44. }else{
45. let current = this.head
46. while(index++ < position){
47. previous = current
48. current = current.next
49. }
50. previous.next = node
51. node.next = current
52. }
53. this.length ++
54. }
55. }
56. /**
57. * 删除元素
58. * @param {*} element 删除的元素
59. * @return {*} 被删除的元素
60. */
61. remove(element){
62. let current = this.head,
63. previous = null
64. if(element === this.head.element){
65. this.head = current.next
66. }else{
67. while(current.next && current.element !== element){
68. previous = current
69. current = current.next
70. }
71. previous.next = current.next
72. this.length --
73. return current.element
74. }
75. }
76. /**
77. * 删除元素（指定位置）
78. * @param {Number} position 删除元素的位置
79. * @return {*} 被删除的元素
80. */
81. removeAt(position){
82. if(position >= 0 && position <= this.length){
83. let current = this.head,
84. index = 0,
85. previous = null
86. if(position === 0){ // 删除第一项
87. this.head = current.next
88. }else{
89. while(index++ < position){
90. previous = current
91. current = current.next
92. }
93. previous.next = current.next
94. }
95. this.length --
96. return current.element
97. }
98. }
99. /**
100. * 查找指定元素的位置
101. * @param {*} element 查找的元素
102. * @return {Number} 查找的元素的下标
103. */
104. indexOf(element){
105. let current = this.head,
106. index = 0
107. while(current.next && current.element !== element){
108. current = current.next
109. index ++
110. }
111. return index === 0 ? -1 : index
112. }
113. /**
114. * 链表是否为空
115. * @return {Boolean}
116. */
117. isEmpty(){
118. return this.length === 0
119. }
120. /**
121. * 链表的长度
122. * @return {Number}
123. */
124. size(){
125. return this.length
126. }
127. /**
128. * 将链表转成字符串
129. * @return {String}
130. */
131. toString(){
132. let current = this.head,
133. arr = new Array()
134. while(current.next){
135. arr.push(current.element)
136. current = current.next
137. }
138. arr.push(current.element)
139. return arr.toString()
140. }
141. }
142.
143. let leo = new LinkedList()
144. leo.append(3)
145. leo.append(6)
146. leo.append(9)
147. console.log(leo.length)
148. console.log(leo.head)
149. leo.remove(6)
150. console.log(leo.length)
151. console.log(leo.head)
152. console.log(leo.toString())三、实现反转链表
用链表的方式，输出一个反转后的单链表。
示例:
1. 输入: 1->2->3->4->5->NULL
2. 输出: 5->4->3->2->1->NULL
3. // input
4. let head = {
5. 'val': 1,'next': {
6. 'val': 2,'next': {
7. 'val': 3,'next': {
8. 'val': 4,'next': {
9. 'val': 5,
10. 'next': null
11. }
12. }
13. }
14. }
15. };
16. reverseList(head)
17.
18. // output
19. head = {
20. 'val': 5,'next': {
21. 'val': 4,'next': {
22. 'val': 3,'next': {
23. 'val': 2,'next': {
24. 'val': 1,
25. 'next': null
26. }
27. }
28. }
29. }
30. };
解题思路1.使用迭代：
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
解题思路2.使用递归：
通过递归修改 head.next.next 和 head.next 指针来实现。
解析：
题目出自：[Leetcode 206. 反转链表] (https://leetcode-cn.com/problems/reverse-linked-list/)
介绍两种常用方法：
1.使用迭代：
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val) {
4. * this.val = val;
5. * this.next = null;
6. * }
7. */
8. /**
9. * @param {ListNode} head
10. * @return {ListNode}
11. */
12. let reverseList = function(head) {
13. let pre = null, curr = head
14. while (curr) {
15. next = curr.next
16. curr.next = pre
17. pre = curr
18. curr = next
19. }
20. return pre
21. };
复杂度分析
时间复杂度： O(n)。 假设 n 是列表的长度，时间复杂度是 O(n)。
空间复杂度： O(1)。
2.使用递归：
1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val) {
4. * this.val = val;
5. * this.next = null;
6. * }
7. */
8. /**
9. * @param {ListNode} head
10. * @return {ListNode}
11. */
12. let reverseList = function(head) {
13. if(head == null || head.next == null) return head
14. let pre = reverseList(head.next)
15. head.next.next = head
16. head.next = null
17. return pre
18. };
复杂度分析
时间复杂度： O(n)。 假设 n 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度： O(n)。 由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。
四、判断链表是否有环
设计一个函数 hasCycle，接收一个链表作为参数，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
需要注意的是，不可能存在多个环，最多只有一个。
示例 1：
-
输入：head = [3,2,0,-4], pos = 1 -
输出：true -
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
-
输入：head = [1,2], pos = 0 -
输出：true -
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
-
输入：head = [1], pos = -1 -
输出：false -
解释：链表中没有环。
解题思路1.判断是否有 null：
一直遍历下去，如果遍历到 null 则表示没有环，否则有环，但是考虑到性能问题，最好给定一段时间作为限制，超过时间就不要继续遍历。
解题思路2.标记法：
也是要遍历每个节点，并在遍历的节点添加标记，如果后面遍历过程中，遇到有这个标记的节点，即表示有环，反之没有环。
解题思路3.使用双指针（龟兔赛跑式）：
设置2个指针，一个 快指针 每次走 2 步， 慢指针 每次走 1 步，如果没有环的情况，最后这两个指针不会相遇，如果有环，会相遇。
解析：
题目出自：[Leetcode 141. 环形链表] (https://leetcode-cn.com/problems/linked-list-cycle/)
1.断是否有 null
1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val) {
4. * this.val = val;
5. * this.next = null;
6. * }
7. */
8.
9. /**
10. * @param {ListNode} head
11. * @return {boolean}
12. */
13. let hasCycle = function(head) {
14. while(head){
15. if(head.value == null) return true
16. head.value = null
17. head = head.next
18. }
19. return false
20. }
2.标记法
1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val) {
4. * this.val = val;
5. * this.next = null;
6. * }
7. */
8.
9. /**
10. * @param {ListNode} head
11. * @return {boolean}
12. */
13. let hasCycle = function(head) {
14. let node = head
15. while(node){
16. if(node.isVisit){
17. return true
18. }else{
19. node.isVisit = true
20. }
21. node = node.next
22. }
23. return false
24. };
3.使用双指针
1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val) {
4. * this.val = val;
5. * this.next = null;
6. * }
7. */
8.
9. /**
10. * @param {ListNode} head
11. * @return {boolean}
12. */
13. let hasCycle = function(head) {
14. if(head == null || head.next == null) return false
15. let slow = head, fast = head.next
16. while(slow != fast){
17. if(fast == null || fast.next == null) return false
18. slow = slow.next // 慢指针每次走1步
19. fast = fast.next.next // 快指针每次走1补
20. }
21. return true
22. };
五、实现两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
-
给定 1->2->3->4, 你应该返回 2->1->4->3. -
给定 1->2->3->4->5, 你应该返回 2->1->4->3->5.
解题思路1.使用迭代：
和反转链表类似，关键在于有三个指针，分别指向前后和当前节点，而不同在于两两交换后，移动节点的步长为2，需要注意。
解题思路2.使用递归：
这里也可以使用递归，也可以参考反转链表的问题，终止条件是递归到链表为空，或者只剩下一个元素没得交换了，才终止。
解析：
题目出自：[Leetcode 24. 两两交换链表中的节点] (https://leetcode-cn.com/problems/swap-nodes-in-pairs/)
介绍两种常用方法：
1.使用迭代：
1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val) {
4. * this.val = val;
5. * this.next = null;
6. * }
7. */
8. /**
9. * @param {ListNode} head
10. * @return {ListNode}
11. */
12. let swapPairs = function (head){
13. if(!head) return null
14. let arr = []
15. while(head){
16. let next = head.next
17. head.next = null
18. arr.push(head)
19. head = next
20. }
21.
22. for(let i = 0; i < arr.length; i += 2){
23. let [a, b] = [arr[i], arr[i + 1]]
24. if(!b) continue
25. [arr[i], arr[i + 1]] = [b, a]
26. }
27.
28. for(let i = 0; i < arr.length - 1; i ++){
29. arr[i].next = arr[i + 1]
30. }
31. return arr[0]
32. }
2.使用递归：
1. /**
2. * Definition for singly-linked list.
3. * function ListNode(val) {
4. * this.val = val;
5. * this.next = null;
6. * }
7. */
8. /**
9. * @param {ListNode} head
10. * @return {ListNode}
11. */
12.
13. let swapPairs = function (head){
14. if(head == null || head.next ==null) return head
15. let next = head.next
16. head.next = swapPairs(next.next)
17. next.next = head
18. return next
19. }
每一个，都是对我最大的肯定！