leetcode题解（7）

Leetcode题解（7）- 2018 力扣 Leetcode CN 高频题汇总 part 3 堆、栈、队列、链表

堆、栈、队列、链表的一些题目。

# 堆、栈、队列
## 最小栈 
Leetcode 155题，之前做过，见 [题解（4）最小栈](https://codingcat.cn/article/79#155-%20%E6%9C%80%E5%B0%8F%E6%A0%88)，思路就是每个元素进栈时记下它进栈前的栈最小值，当它pop时就能知道它pop之后栈的最小值是多少了。
## 数组中的第K个最大元素 
Leetcode 215题。
### 问题 
在未排序的数组中找到第 k 大的元素。
示例 1: 
``` 
输入: [3,2,1,5,6,4] 和 k = 2 
输出: 5 
```
示例 2: 
``` 
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 
输出: 4 
``` 
### 思路 
思路类似之前剑指Offer的 [最小的k个数](https://codingcat.cn/article/28#%E6%9C%80%E5%B0%8F%E7%9A%84K%E4%B8%AA%E6%95%B0) 
- 简单粗暴的排序法 
先排序，然后直接取第k位置就可以
- 冒泡 
类似于冒泡排序的思路，从小往大冒泡，冒k次之后就得到第k大的数了
- 小根堆 
维护一个小根堆，遍历数组，如果当前元素大于根，则加入堆中；如果加入后堆的元素数量多于k，则弹出根元素。 遍历一遍之后，根就是第k大的元素。
- 类似快排的划分思路 
先任取一个数，把比它大的数移动到它的左边，比它小的数移动到它的右边。移动完成一轮后，看该数的下标（从0计数），如果刚好为k-1则它就是第k大的数，如果小于k-1，说明第k大的数在它右边，如果大于k-1则说明第k大的数在它左边，取左边或者右边继续进行移动，直到找到。
### 代码 
这里练习实现一个划分的代码吧。（这段写的还真是曲折艰难 
``` 
class Solution: 
 def findKthLargest(self, nums: List[int], k: int) -> int: 
 return self.find(nums, k, 0, len(nums) - 1)
 def find(self, nums, k, left, right): 
 # 每次partition取最左边的数作为基准，进行调整，把大于等于它的放到它左边，小于它的放到右边，返回调整后该数的位置 
 target = self.partition(nums, left, right) 
 if target == k - 1: # 刚好第k个则完成 
 return nums[target] 
 elif target < k - 1: # 没有找到则继续调整 
 return self.find(nums, k, target + 1, right) 
 elif target > k - 1: 
 return self.find(nums, k, left, target - 1) 
 return None
 # 下面这段代码建议在纸上仔细推演一番过程，不然有点不太好理解 
 def partition(self, nums, l, r): 
 # 取最左边元素作为目标，目标值 t_value 
 t_value = nums[l] 
 t = l 
 i = l + 1 
 while i <= r: 
 if nums[i] >= t_value: 
 t += 1 
 nums[i], nums[t] = nums[t], nums[i] 
 i += 1 
 nums[l], nums[t] = nums[t], nums[l] 
 return t
```
## 数据流的中位数 
Leetcode 295题 
### 问题 
中位数是【有序列表】中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
设计一个支持以下两种操作的数据结构： 
void addNum(int num) - 从数据流中添加一个整数到数据结构中。 
double findMedian() - 返回目前所有元素的中位数。
进阶: 
如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？ 
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
### 思路 
一种思路可以利用两个堆：一个大根堆，一个小根堆。来了一个元素之后，如果小于大根堆的堆顶，则加入大根堆；如果大于小根堆的堆顶，则加入小根堆，然后判断下两个堆的情况，始终保证两个堆元素数量相等，或者差1，否则需要pop调整。取中位数时，如果元素数量相等，则只要将两个堆顶元素平均，如果不等，则从元素多的那个里取堆顶。
另一种思路就是排序的思路，类似插入排序，每来一个新的元素，通过二分查找的方式找到该元素应该插入的位置，所以存储的一直是一个有序列表。要取中位数时，直接取中间位置的一个或者两个数均值就可以。
### 代码 
按照第二种思路来写代码： 
``` 
class MedianFinder:
 def __init__(self): 
 """ 
 initialize your data structure here. 
 """ 
 self.data = []
 def binaryInsert(self, num): 
 l, r = 0, len(self.data) - 1 
 while l <= r: 
 if num >= self.data[r]: 
 self.data.insert(r+1, num) 
 return 
 elif num <= self.data[l]: 
 self.data.insert(l, num) 
 return 
 mid = (l + r) // 2 
 if self.data[mid] == num: 
 self.data.insert(mid, num) 
 return 
 elif self.data[mid] > num: 
 r = mid - 1 
 else: 
 l = mid + 1
 def addNum(self, num: int) -> None: 
 if len(self.data) == 0: 
 self.data.append(num) 
 return 
 # 二分查找加入 
 self.binaryInsert(num)
 def findMedian(self) -> float: 
 if not self.data: 
 return None 
 mid = len(self.data) // 2 
 if len(self.data) % 2 == 0: 
 return (self.data[mid] + self.data[mid - 1]) / 2 
 else: 
 return self.data[mid]
# Your MedianFinder object will be instantiated and called as such: 
# obj = MedianFinder() 
# obj.addNum(num) 
# param_2 = obj.findMedian() 
```
## 有序矩阵中第k小的元素 
Leetcode 378题
### 问题 
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
示例: 
``` 
matrix = [ 
 [ 1, 5, 9], 
 [10, 11, 13], 
 [12, 13, 15] 
], 
k = 8， 返回 13。 
```
### 思路 
暴力法就不考虑了吧，整个矩阵展平成一个数组，排序取。
容易理解的思路就是多路归并排序。既然每一行都是有序的，那可以用n个指针进行多路归并，归并到第k个元素就是第k小的元素了。
也可以用容量为k的大根堆，遍历一遍，取堆顶元素就是第k小的。
此外还有个二分查找法来做，感觉不是那么容易理解，从别处粘贴过来一段描述：
> 二分查找法来做，我们由于是有序矩阵，那么左上角的数字一定是最小的，而右下角的数字一定是最大的，所以这个是我们搜索的范围，然后我们算出中间数字mid，由于矩阵中不同行之间的元素并不是严格有序的，所以我们要在每一行都数一下有多少个元素的值比mid小, 并把这个值加起来，假设是t，此时我们就知道mid是第t+1小的数了。然后t与k比较，如果t比k大说明应该进一步把mid值变小，如果t比k小说明应该把mid值变大。按此进行二分查找，left和right最终会相等，并且会变成数组中第k小的数字。
``` 
举个例子来说吧，比如数组为: 
[1 2 
12 100] 
k = 3 
那么刚开始left = 1, right = 100, mid = 50, 遍历完 cnt = 3，此时right更新为50 
此时left = 1, right = 50, mid = 25, 遍历完之后 cnt = 3, 此时right更新为25 
此时left = 1, right = 25, mid = 13, 遍历完之后 cnt = 3, 此时right更新为13 
此时left = 1, right = 13, mid = 7, 遍历完之后 cnt = 2, 此时left更新为8 
此时left = 8, right = 13, mid = 10, 遍历完之后 cnt = 2, 此时left更新为11 
此时left = 11, right = 12, mid = 11, 遍历完之后 cnt = 2, 此时left更新为12 
循环结束，left和right均为12，任意返回一个即可。 
```
### 代码 
按多路归并来写一个吧 
``` 
import sys
class Solution: 
 def kthSmallest(self, matrix: List[List[int]], k: int) -> int: 
 rows = len(matrix) 
 cols = len(matrix[0]) 
 cursors = [0] * rows 
 cnt = 0 
 ans = None 
 while cnt < k: 
 min_val = sys.maxsize 
 min_row = None 
 for i in range(0, rows): 
 if cursors[i] >= cols: 
 continue 
 if matrix[i][cursors[i]] < min_val: 
 min_val = matrix[i][cursors[i]] 
 min_row = i 
 cursors[min_row] += 1 
 ans = min_val 
 cnt += 1 
 return ans 
```
多路归并提交时大的case超时了，只好找了一个二分查找版本，而且实际leetcode提交后执行效率还奇高hhhh： 
``` 
class Solution: 
 def kthSmallest(self, matrix: List[List[int]], k: int) -> int: 
 n = len(matrix) 
 lo = matrix[0][0] 
 hi = matrix[n-1][n-1] 
 while lo < hi: 
 mid = (lo + hi) // 2 
 j = n - 1 
 count = 0 
 for i in range(n): 
 if j == -1: 
 break 
 while j >= 0 and matrix[i][j] > mid: 
 j -= 1 
 count += (j+1) 
 if count < k: 
 lo = mid + 1 
 else: 
 hi = mid 
 return lo 
```
## 前k个高频元素 
Leetcode 347题
### 问题 
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
``` 
示例 1: 
输入: nums = [1,1,1,2,2,3], k = 2 
输出: [1,2]
示例 2: 
输入: nums = [1], k = 1 
输出: [1] 
```
说明： 
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小
### 思路 
首先要统计频率，这个使用map来做，然后是选取 top k 频率的元素了，这块可以粗暴的进行排序然后取前k，也可以利用最小堆来做，或者用类似桶的方式（建一个长度为n的数组，下标即代表出现次数，把各个元素放到对应的桶内，然后按下标从大到小取k个不空的桶就可以）
### 代码 
``` 
class Solution: 
 def topKFrequent(self, nums: List[int], k: int) -> List[int]: 
 info = {} 
 for n in nums: 
 if n not in info: 
 info[n] = 1 
 else: 
 info[n] += 1 
 data = [None] * (len(nums) + 1) 
 for key, v in info.items(): 
 if data[v]: 
 data[v].append(key) 
 else: 
 data[v] = [key, ] 
 result = [] 
 for i in range(len(data)-1, -1, -1): 
 if k <= 0: 
 break 
 if data[i]: 
 result.extend(data[i]) 
 k -= len(data[i]) 
 return result
```
## 滑动窗口最大值 
Leetcode 239题
### 问题 
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位，返回滑动窗口最大值。
``` 
示例: 
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 
输出: [3,3,5,5,6,7] 
解释: 
 滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3 
 1 [3 -1 -3] 5 3 6 7 3 
 1 3 [-1 -3 5] 3 6 7 5 
 1 3 -1 [-3 5 3] 6 7 5 
 1 3 -1 -3 [5 3 6] 7 6 
 1 3 -1 -3 5 [3 6 7] 7
```
能否在线性时间复杂度解决。
### 思路 
这个题详见剑指Offer [这里](https://codingcat.cn/article/52#%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E7%9A%84%E6%9C%80%E5%A4%A7%E5%80%BC)，使用双向队列来存储滑动窗口中的元素，不再重复写思路了。
### 代码 
``` 
class Solution: 
 def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: 
 ans = [] 
 length = len(nums) 
 if k <= 0 or k > length or not nums: 
 return [] 
 deque = [] 
 for i in range(0, len(nums)): 
 while deque and nums[deque[-1]] < nums[i]: 
 deque.pop() 
 deque.append(i) 
 if i - deque[0] + 1 > k: 
 deque.pop(0) 
 if i >= k - 1: 
 ans.append(nums[deque[0]]) 
 return ans 
```
## 基本计算器 II 
Leetcode 227题
### 问题 
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含<code>非负整数，+， - ，*，/ 四种运算符和空格</code> 。 整数除法仅保留整数部分。可以假定所有输入表达式都是有效的。
示例： 
``` 
输入: " 3+5 / 2 " 
输出: 5 
```
### 思路 
思路就是利用栈来解决，从前往后读取这个字符串，遇到数字则入栈，加减法也入栈，遇到乘除则立即进行计算，并将计算结果入栈。然后从顶上开始出栈并对加减法进行计算，得到最终结果。
### 代码 
按上面思路实现代码： 
``` 
class Solution: 
 def calculate(self, s: str) -> int: 
 d = 0 
 prev_sign = '+' 
 data = [] 
 for i, c in enumerate(s): 
 if ord(c) >= ord('0'): #【1】 
 d = d * 10 - ord('0') + ord(c) # 【2】 
 if (c != ' ' and ord(c) < ord('0')) or i == len(s) - 1: #【3】 
 if prev_sign == '+': 
 data.append(d) 
 elif prev_sign == '-': 
 data.append(-d) 
 elif prev_sign == '*': 
 prev = data.pop() 
 data.append(d * prev) 
 elif prev_sign == '/': #【4】 
 prev = data.pop() 
 if prev < 0: 
 data.append(-1 * ((-1 * prev) // d)) 
 else: 
 data.append( prev // d) 
 prev_sign = c 
 d = 0 
 res = 0 
 for n in data: 
 res += n 
 return res 
``` 
需要做一些说明。
1）加减乘除和空格符号的ascii都是小于‘0’的ascii的，所以1处用于判断是数字还是符号。而且因为在读取时是一位一位读的，我们需要手动进行字符串转数字的拼凑。
2）先减0再加c的原因是避免先加c导致数值过大溢出
3）要单独考虑最后一个字符的情况，因为按照实现的逻辑，是遇到符号后，才会将当前数字d加入栈中，而最后一个数字的后面不会再有符号了，所以需要单独处理，如果当前字符是最后一个字符了的话，也需要将当前积累的数字d进行入栈处理。
4）入栈时我们采用了将减法变成负值入栈的情况，但这在计算除法时会导致一个问题，例如 
<code>14-3/2</code>这个式子，按我们的方法，最终会计算 -3/2 ，但是在python里算出的结果是 -2，最终值是14-2=12，但是按照正常来算的话 应该是先算3/2得到1，最终值是14-1=13。所以这里只好处理了一下，遇到减法相除的话就先变成正数相除再相减。
## 扁平化嵌套列表迭代器 
leetcode 341题
### 问题 
给定一个嵌套的整型列表。设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
列表中的项或者为一个整数，或者是另一个列表。 
``` 
示例 
输入: [1,[4,[6]]] 
输出: [1,4,6] 
解释: 通过重复调用 next 直到 hasNext 返回false，next 返回的元素的顺序应该是: [1,4,6]。 
```
### 思路 
有的做法是一开始时就通过递归方式，把整个数组展平并存储，将来取用就只要按顺序返回即可，但这个感觉就不是典型的迭代器的意思了。
另外的思路是通过各种标记指针的方式，来逐个进行出入。
### 代码 
先列一个dfs代码吧，初始化时就把列表展平了，容易理解。 
``` 
class NestedIterator(object):
 def __init__(self, nestedList): 
 """ 
 Initialize your data structure here. 
 :type nestedList: List[NestedInteger] 
 """ 
 def FlattenMain(l): 
 def flatten(l): 
 res = [] 
 for e in l: 
 if e.isInteger(): 
 res.append(e.getInteger()) 
 else: 
 res += flatten(e.getList()) 
 return res 
 return flatten(l) 
 self.list = FlattenMain(nestedList) 
 self.l = len(self.list) 
 self.i = -1
 def next(self): 
 """ 
 :rtype: int 
 """ 
 self.i += 1 
 return self.list[self.i]
 def hasNext(self): 
 """ 
 :rtype: bool 
 """ 
 if self.i+1<self.l: 
 return True 
 else: 
 return False 
```
再列一个迭代的方法吧： 
``` 
class NestedIterator(object):
 def __init__(self, nestedList): 
 self.nestedList = nestedList 
 self.index = 0 
 self.temp_nested_list = None 
 self.length = len(self.nestedList)
 def next(self): 
 if self.temp_nested_list: 
 return self.temp_nested_list.next() 
 else: 
 self.index += 1 
 return self.nestedList[self.index - 1].getInteger()
 def hasNext(self): 
 if self.index >= self.length: 
 return False 
 elif self.temp_nested_list: #如果临时变量为嵌套迭代器 
 if self.temp_nested_list.hasNext(): #且拥有下一个整数 
 return True #此时next()会返回嵌套迭代器的next()整数 
 else: 
 self.temp_nested_list = None #否则置空索引+1重新判断 
 self.index += 1 
 return self.hasNext() 
 else: #临时变量为空 
 if self.nestedList[self.index].isInteger(): #当前索引元素为整数，next直接返回索引整数且索引+1 
 return True 
 else: #当前索引元素为嵌套，临时变量赋值为嵌套迭代器对象 
 self.temp_nested_list = NestedIterator(self.nestedList[self.index].getList()) 
 return self.hasNext() #重新调用判断 
```
再列一个我写的方法吧，个人感觉没啥毛病，拿本地python也能跑过的用例，但是leetcode基本的用例都超时跑不过，也是很心累了……（不过下面的代码对 <code>[[]]</code>这种的处理有欠缺会死循环，大概也是有点问题的吧），还是参考下上面给出的就行。 
``` 
class NestedIterator(object):
 def __init__(self, nestedList): 
 """ 
 Initialize your data structure here. 
 :type nestedList: List[NestedInteger] 
 """ 
 self.data = [] 
 self.data.append([nestedList, 0])
 def next(self): 
 """ 
 :rtype: int 
 """ 
 if self.data: 
 info, index = self.data[-1] 
 while info and info[index] and type(info[index]) == list: 
 if index < len(info) - 1: 
 self.data[-1][1] += 1 
 else: 
 self.data.pop() 
 info, index = info[index], 0 
 self.data.append([info, index]) 
 if info and info[index] and type(info[index]) == int: 
 ret = info[index] 
 if index < len(info) - 1: 
 self.data[-1][1] += 1 
 else: 
 self.data.pop() 
 return ret
 def hasNext(self): 
 """ 
 :rtype: bool 
 """ 
 return True if self.data else False 
```
## 逆波兰表达式求值 
Leetcode 150题
### 问题 
根据逆波兰表示法，求表达式的值。
有效的运算符包括<code> +, -, *, /</code> 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明： 
整数除法只保留整数部分。 
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
``` 
示例 1： 
输入: ["2", "1", "+", "3", "*"] 
输出: 9 
解释: ((2 + 1) * 3) = 9
示例 2： 
输入: ["4", "13", "5", "/", "+"] 
输出: 6 
解释: (4 + (13 / 5)) = 6 
``` 
### 思路 
逆波兰式又叫后缀表达式，也就是说操作符写在运算后面。这样一想这个题其实就很简单了，比之前的基本计算器要简单，利用栈就可以轻松完成。
### 代码 
``` 
class Solution(object):
 def isdigit(self, num): 
 try: 
 n = int(num) 
 return True 
 except: 
 return False
 def evalRPN(self, tokens): 
 """ 
 :type tokens: List[str] 
 :rtype: int 
 """ 
 data = [] 
 for c in tokens: 
 if self.isdigit(c): 
 data.append(int(c)) 
 else: 
 prev = data.pop() 
 prev2 = data.pop() 
 if c == '+': 
 data.append(prev2 + prev) 
 elif c == '-': 
 data.append(prev2 - prev) 
 elif c == '*': 
 data.append(prev2 * prev) 
 elif c == '/': 
 data.append(int(prev2 / prev)) 
 return data[0] 
```
上述代码实际中遇到一些问题，看似简单的问题在写出来的时候也有暗藏的坑，不能盲目自大啊。
一开始判断数字时使用了 strxxx.isdigit()，这个是不可以的，因为它会把 ‘-1’这样的判断为false。另外就是python除法的坑了，比如像 <code>6 / -132</code>，按题目要求，这个应该值为0， 但在python里如果用<code>6 // -132</code> 的话会向下取整，值为-1。所以要用 <code>int(prev2/prev)</code>这样的写法了。而且python2和3对于左斜线 / 的含义也不同（2是整除，3是精确除），在做题时也一定要注意python版本啊！
# 链表
## 复制带随机指针的链表 
Leetcode 138题，也是剑指offer中的“复杂链表的复制”
### 问题和思路 
之前已经有详细的图解和说明啦，[直接看这里](https://codingcat.cn/article/27#%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6)，不过之前的代码是按照思路2来写的，这里补充一个按照思路3来写的吧。
### 代码 
``` 
""" 
# Definition for a Node. 
class Node: 
 def __init__(self, val, next, random): 
 self.val = val 
 self.next = next 
 self.random = random 
""" 
class Solution: 
 def copyRandomList(self, head: 'Node') -> 'Node': 
 if not head: 
 return None 
 # 复制节点 
 p = head 
 while p: 
 n = Node(p.val, p.next, None) 
 p.next = n 
 p = n.next 
 # 处理random指针 
 p = head 
 while p: 
 n = p.next 
 if p.random: # 注意random指针是空的情况 
 n.random = p.random.next 
 p = n.next 
 # 拆分链表 
 p = head 
 n_head = p.next 
 while p: 
 n = p.next 
 p.next = n.next 
 if n.next: # 要判空，避免链表到尾部时的情况 
 n.next = n.next.next 
 p = p.next 
 return n_head
```
## 环形链表 
判断链表中是否有环，Leetcode 141题，之前写过了，见 [剑指offer-链表中环的入口结点](https://codingcat.cn/article/48#%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%8E%AF%E7%9A%84%E5%85%A5%E5%8F%A3%E7%BB%93%E7%82%B9)，这篇文章也同时说明了 leetcode 142题 环形链表 II（也就是要求环的入口）。
## 排序链表 
Leetcode 148题。
### 问题 
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
### 思路 
由于要求 O(n log n) 的复杂度，采用归并排序。先用快慢指针找到链表中点，一分为二，一直拆分下去直到分成单个，然后再两两归并。归并的思路和代码要尽量熟记啊。
### 代码 
``` 
# Definition for singly-linked list. 
# class ListNode(object): 
# def __init__(self, x): 
# self.val = x 
# self.next = None
class Solution(object): 
 def sortList(self, head): 
 """ 
 :type head: ListNode 
 :rtype: ListNode 
 """ 
 if head: 
 return self.mergeSort(head) 
 else: 
 return None
 def mergeSort(self, head): 
 # 分裂链表到单个节点后不再分裂 
 if not head.next: 
 return head 
 # 快慢指针查找中间点 
 p, q, pre = head, head, None 
 while q and q.next: 
 pre = p 
 p = p.next 
 q = q.next.next 
 # 分裂链表为两段，两段继续进行分裂 
 pre.next = None 
 l = self.mergeSort(head) 
 r = self.mergeSort(p) 
 return self.merge(l, r)
 def merge(self, l, r): 
 # 归并 
 head = ListNode(0) 
 cur = head 
 while l and r: 
 if l.val <= r.val: 
 cur.next = l 
 cur = cur.next 
 l = l.next 
 else: 
 cur.next = r 
 cur = cur.next 
 r = r.next 
 if l: 
 cur.next = l 
 if r: 
 cur.next = r 
 return head.next
```
## 相交链表 
Leetcode 160题，之前做过，见[leetcode 160 相交链表](https://codingcat.cn/article/79#160-%20%E7%9B%B8%E4%BA%A4%E9%93%BE%E8%A1%A8)
## 反转链表 
Leetcode 206题。
### 问题及思路 
反转链表真的非常经典了，但一定不要得意忘形，注意细节不要有遗漏：返回值应该是新的头指针，以及原来的头指针的next应该为None。
### 代码 
``` 
class Solution(object): 
 def reverseList(self, head): 
 """ 
 :type head: ListNode 
 :rtype: ListNode 
 """ 
 if not head or not head.next: 
 return head 
 pre, c = head, head.next 
 pre.next = None 
 while c: 
 n = c.next 
 c.next = pre 
 pre = c 
 c = n 
 return pre 
```
## 回文链表 
### 问题 
判断一个链表是否是回文链表
### 思路
- 借助栈，先压栈后弹栈，弹栈时相当于逆序，与列表比较元素即可。栈可以优化下，用快慢指针找到中点，只将前一半元素入栈，继续遍历链表后一半时弹栈进行比较即可。栈需要开辟n的额外的空间。
- 也可以反转链表然后比较，同时也是优化成只反转一半链表，就可以开始比较，或者是整条链表反转，只比较到中间就可以了。反转链表不需要额外开辟n的空间，但是会导致原链表被改坏。
### 代码 
代码按照栈来写了：
``` 
class Solution(object): 
 def isPalindrome(self, head): 
 """ 
 :type head: ListNode 
 :rtype: bool 
 """ 
 if not head: 
 return True 
 # 快慢指针找中点，前一半链表入栈 
 stack = [] 
 p, q = head, head 
 while p and p.next: 
 stack.append(q) 
 p = p.next.next 
 q = q.next 
 # 处理奇偶长度 
 if p: 
 q = q.next 
 # 弹栈，判断回文 
 while q: 
 s = stack.pop() 
 if s.val != q.val: 
 return False 
 q = q.next 
 return True 
```
## 删除链表的节点 
Leetcode 237题
### 问题 
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
### 思路 
常规思路就是要从头遍历，找到当前节点的前一个节点pre，将pre的指针变成当前的next，然后删掉当前节点。
但本题目中，一种更巧妙的思路是将next节点的值赋给当前节点，然后删掉next节点。因为题目要求中已经明确说明了节点并非末尾节点，所以节点一定有next节点。
### 代码 
可以说是很过分了哈哈
``` 
class Solution(object): 
 def deleteNode(self, node): 
 node.val = node.next.val 
 node.next = node.next.next 
```
## 奇偶链表 
Leetcode 328题。
### 问题 
给定一个单链表，把所有的序号是奇数节点和偶数节点分别排在一起，例如原来是 12345，排完之后是 13524.
算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
### 思路 
一边从前往后遍历，一边将奇偶拆分拼接成两条，最后将偶数条接在奇数条的后面即可。
### 代码 
``` 
class Solution(object): 
 def oddEvenList(self, head): 
 """ 
 :type head: ListNode 
 :rtype: ListNode 
 """ 
 if not head or not head.next: 
 return head 
 o = head 
 p = head.next 
 e = p 
 while o.next and e.next: 
 o.next = e.next 
 o = o.next 
 e.next = o.next 
 e = e.next 
 o.next = p 
 return head 
```

leetcode题解（7）

Leetcode题解（7）- 2018 力扣 Leetcode CN 高频题汇总 part 3 堆、栈、队列、链表

近期文章

近期评论

标签

热门

文章归档

分类目录

功能