Leetcode题解（7）- 2018 力扣 Leetcode CN 高频题汇总 part 3 堆、栈、队列、链表
# 堆、栈、队列
# 最小栈
Leetcode 155题，之前做过，见 题解（4）最小栈 (opens new window)，思路就是每个元素进栈时记下它进栈前的栈最小值，当它pop时就能知道它pop之后栈的最小值是多少了。
# 数组中的第K个最大元素
Leetcode 215题。
# 问题
在未排序的数组中找到第 k 大的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
2
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
2
# 思路
思路类似之前剑指Offer的 最小的k个数 (opens new window)
简单粗暴的排序法 先排序，然后直接取第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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 数据流的中位数
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()
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# 有序矩阵中第k小的元素
Leetcode 378题
# 问题
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。
示例:
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8， 返回 13。
2
3
4
5
6
# 思路
暴力法就不考虑了吧，整个矩阵展平成一个数组，排序取。
容易理解的思路就是多路归并排序。既然每一行都是有序的，那可以用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，任意返回一个即可。
2
3
4
5
6
7
8
9
10
11
# 代码
按多路归并来写一个吧
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
多路归并提交时大的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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 前k个高频元素
Leetcode 347题
# 问题
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
2
3
4
5
6
7
说明：
- 你可以假设给定的 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 滑动窗口最大值
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
2
3
4
5
6
7
8
9
10
11
12
13
14
能否在线性时间复杂度解决。
# 思路
这个题详见剑指Offer 这里 (opens new window)，使用双向队列来存储滑动窗口中的元素，不再重复写思路了。
# 代码
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 基本计算器 II
Leetcode 227题
# 问题
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。可以假定所有输入表达式都是有效的。
示例：
输入: " 3+5 / 2 "
输出: 5
2
# 思路
思路就是利用栈来解决，从前往后读取这个字符串，遇到数字则入栈，加减法也入栈，遇到乘除则立即进行计算，并将计算结果入栈。然后从顶上开始出栈并对加减法进行计算，得到最终结果。
# 代码
按上面思路实现代码：
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
需要做一些说明。
1）加减乘除和空格符号的ascii都是小于‘0’的ascii的，所以1处用于判断是数字还是符号。而且因为在读取时是一位一位读的，我们需要手动进行字符串转数字的拼凑。
2）先减0再加c的原因是避免先加c导致数值过大溢出
3）要单独考虑最后一个字符的情况，因为按照实现的逻辑，是遇到符号后，才会将当前数字d加入栈中，而最后一个数字的后面不会再有符号了，所以需要单独处理，如果当前字符是最后一个字符了的话，也需要将当前积累的数字d进行入栈处理。
4）入栈时我们采用了将减法变成负值入栈的情况，但这在计算除法时会导致一个问题，例如
14-3/2这个式子，按我们的方法，最终会计算 -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]。
2
3
4
# 思路
有的做法是一开始时就通过递归方式，把整个数组展平并存储，将来取用就只要按顺序返回即可，但这个感觉就不是典型的迭代器的意思了。
另外的思路是通过各种标记指针的方式，来逐个进行出入。
# 代码
先列一个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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
再列一个迭代的方法吧：
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() #重新调用判断
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
再列一个我写的方法吧，个人感觉没啥毛病，拿本地python也能跑过的用例，但是leetcode基本的用例都超时跑不过，也是很心累了……（不过下面的代码对 [[]]这种的处理有欠缺会死循环，大概也是有点问题的吧），还是参考下上面给出的就行。
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 逆波兰表达式求值
Leetcode 150题
# 问题
根据逆波兰表示法，求表达式的值。
有效的运算符包括+, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明： 整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6
2
3
4
5
6
7
8
9
# 思路
逆波兰式又叫后缀表达式，也就是说操作符写在运算后面。这样一想这个题其实就很简单了，比之前的基本计算器要简单，利用栈就可以轻松完成。
# 代码
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]
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
上述代码实际中遇到一些问题，看似简单的问题在写出来的时候也有暗藏的坑，不能盲目自大啊。
一开始判断数字时使用了 strxxx.isdigit()，这个是不可以的，因为它会把 ‘-1’这样的判断为false。另外就是python除法的坑了，比如像 6 / -132，按题目要求，这个应该值为0， 但在python里如果用6 // -132 的话会向下取整，值为-1。所以要用 int(prev2/prev)这样的写法了。而且python2和3对于左斜线 / 的含义也不同（2是整除，3是精确除），在做题时也一定要注意python版本啊！
# 链表
# 复制带随机指针的链表
Leetcode 138题，也是剑指offer中的“复杂链表的复制”
# 问题和思路
之前已经有详细的图解和说明啦，直接看这里 (opens new window)，不过之前的代码是按照思路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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 环形链表
判断链表中是否有环，Leetcode 141题，之前写过了，见 剑指offer-链表中环的入口结点 (opens new window)，这篇文章也同时说明了 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 相交链表
Leetcode 160题，之前做过，见leetcode 160 相交链表 (opens new window)
# 反转链表
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 回文链表
# 问题
判断一个链表是否是回文链表
# 思路
借助栈，先压栈后弹栈，弹栈时相当于逆序，与列表比较元素即可。栈可以优化下，用快慢指针找到中点，只将前一半元素入栈，继续遍历链表后一半时弹栈进行比较即可。栈需要开辟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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 删除链表的节点
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
2
3
4
# 奇偶链表
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18