LeetCode Cookbook 链表习题 下篇
?? 开始 链表系列中比较难的或更加综合性质的习题，本篇共有12道题，下周有面试，希望顺利些，努力，奋斗！
707. 设计链表
题目链接：707. 设计链表
题目大意：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
- get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
- addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
- addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
- addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
- deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
例如：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
解题思路：中规中矩的一道题，非常的综合，这里用得是单链表，多学学这种难写的、比较长的代码题，其实本题分开看每一部分都非常 easy，但合起来就不容易一次性完整地写出来，还是需要练习学习。
class ListNode:
def __init__(self,val=0,next=None):
self.val = val
self.next = None
class MyLinkedList:
def __init__(self):
self.size = 0
self.head = ListNode(0)
def get(self, index: int) -> int:
"""
Get the value of the index-th node in the linked list.
If the index is invalid, return -1.
"""
if index<0 or index>=self.size:
return -1
cur = self.head
for _ in range(index+1):
cur = cur.next
return cur.val
def addAtIndex(self, index: int, val: int) -> None:
if index > self.size: return
if index < 0: index = 0
self.size += 1
prev = self.head
for _ in range(index):
prev = prev.next
add = ListNode(val)
add.next = prev.next
prev.next = add
"""
1 -> 2 -> 4 -> 5 -> 6
3 -> 4 -> 5 -> 6
1 -> 2 ->
1 -> 2 -> 3 -> 4 -> 5 -> 6
"""
def deleteAtIndex(self, index: int) -> None:
if index<0 or index>=self.size: return
self.size -= 1
prev = self.head
for _ in range(index):
prev = prev.next
prev.next = prev.next.next
def addAtHead(self, val: int) -> None:
self.addAtIndex(0,val)
def addAtTail(self, val: int) -> None:
self.addAtIndex(self.size,val)
# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)
86. 分隔链表（model-I）
题目链接：86. 分隔链表
题目大意：给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。
例如：
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
解题思路： 这是非常一道综合的、基础题型，主要是使用两个子链表分别存储小于或不小于 x 的结点，最后合并一下。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
l1,l2 = ListNode(),ListNode()
cur1,cur2 = l1,l2
while head:
if head.val<x:
# we can modify in the same station
# so we can not use cur = head
cur1.next = head
cur1 = cur1.next
else:
cur2.next = head
cur2 = cur2.next
head = head.next
cur1.next = l2.next
cur2.next = None
return l1.next
234. 回文链表（model-I 延展题目1）
题目链接：234. 回文链表
题目大意：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
例如：
输入：head = [1,2,2,1]
输出：true
解题思路：与 86. 分隔链表 很相像，不过返回的是真伪 判断一下即可，需要用到 876. 链表的中间结点（Base-I）和 206. 反转链表（Base-II） 可以看我的上一篇博客 这是链接 LeetCode Cookbook 链表习题 上篇
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# 与 143.重排链表 联系起来
if not head or not head.next: return True
# find middle listnode
slow,fast = head,head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 翻转后半部分链表
prev = None
cur = slow
while cur:
tmp = cur.next
cur.next = prev
prev = cur
cur = tmp
# judge True or not
while head != slow:
if head.val != prev.val:
return False
head,prev = head.next,prev.next
return True
328. 奇偶链表（model-I 延展题目2）
题目链接： 328. 奇偶链表
题目大意： 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
例如:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
解题思路：与 86. 分隔链表 一样，非常不错的题。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 86.分隔链表 非常相近的做法
l1,l2 = ListNode(),ListNode()
odd,even = l1,l2
cnt = 1
while head:
if cnt % 2 == 1:
odd.next = head
odd = odd.next
else:
even.next = head
even = even.next
head = head.next
cnt += 1
even.next = None
odd.next = l2.next
return l1.next
725. 分隔链表（model-I 延展题目3）
题目链接：725. 分隔链表
题目大意：给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。返回一个由上述 k 部分组成的数组。
例如：
例如：
输入：head = [1,2,3], k = 5
输出：[[1],[2],[3],[],[]]
解释：第一个元素 output[0] 为 output[0].val = 1 ，output[0].next = null 。
最后一个元素 output[4] 为 null ，但它作为 ListNode 的字符串表示是 []
解题思路： 非常有趣的一道题 和 86. 分隔链表 相似，但有一些细节需要注意，记住每个子链表需要断掉尾巴。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
cur,n = head,0
while cur:
n += 1
cur = cur.next
a,b = n//k,n%k
cur,ans,idx = head,[None]*k,0
while cur:
ans[idx] = cur
prev = None
# a+(idx<b)
for _ in range(a+(idx<b)):
prev = cur
cur = cur.next
idx += 1
# 记住断掉尾巴
prev.next = None
return ans
143. 重排链表（model-I 延展题目4）
题目链接：143. 重排链表I
题目大意：给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L
0
→
L
1
→
…
→
L
n
?
1
→
L
n
L_0 → L_1 → … → L_{n - 1} → L_n
L0?→L1?→…→Ln?1?→Ln?
请将其重新排列后变为：
L
0
→
L
n
→
L
1
→
L
n
?
1
→
L
2
→
L
n
?
2
→
…
L_0 → L_n → L_1 → L_{n - 1} → L_2 → L_{n - 2} → …
L0?→Ln?→L1?→Ln?1?→L2?→Ln?2?→…
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
例如：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]
解题思路： 三步走：（1）找中点 ；（2）右端反转；（3）合并了。 打开链接这三部分分别对应： 对应 876. 链表的中间结点（Base-I） 206. 反转链表（Base-II）21. 合并两个有序链表（Base-VII）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head: return
mid = self.midNode(head)
l1,l2 = head,mid.next
mid.next = None
l2 = self.reverseNode(l2)
while l1 and l2:
l1_tmp,l2_tmp = l1.next,l2.next
l1.next,l1 = l2,l1_tmp
l2.next,l2 = l1,l2_tmp
def midNode(self,head: ListNode) -> ListNode:
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseNode(self,head: ListNode) -> ListNode:
# 形成一个 以prev开头的新链表
prev = None
curr = head
while curr:
nextTmp = curr.next
curr.next = prev
prev = curr
curr = nextTmp
return prev
148. 排序链表（model-I 延展题目5）
题目链接：148. 排序链表
题目大意：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
例如：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
解题思路： 代码注释写得已经非常详细了，仍然是 中点 合并 好吧。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next: return head
# 区别于 876.链表的中间结点 我们需要的是全部分开 便是两个
# 当递归至只有两个元素时 fast = head.next 可以避免原地踏步
# 如果 slow,fast = head,head 只有两个元素时,
# 两个指针会原地踏步 令程序陷入死循环
slow,fast = head,head.next
while fast and fast.next:
fast,slow = fast.next.next,slow.next
# 把 长串 分解成为小串 断开后面的内容
mid,slow.next = slow.next,None
left,right = self.sortList(head),self.sortList(mid)
# 合并 left 和 right
cur = dummy = ListNode(0)
while left and right:
if left.val < right.val:
cur.next,left = left,left.next
else:
cur.next,right = right,right.next
cur = cur.next
cur.next = left if left else right
return dummy.next
25. K 个一组翻转链表（model-I 延展题目6 plus）
题目链接：25. K 个一组翻转链表
题目大意：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
例如：
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
解题思路：综合题 无外乎 找点 翻转 ，代码非常清晰。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
# 翻转获取一个新的子链表，并返回头与尾
def reverse(self,head:ListNode,tail:ListNode):
prev = tail.next
p = head
while prev != tail:
nex = p.next
p.next = prev
prev = p
p = nex
return tail,head
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(-1)
dummy.next = head
prev = dummy
while head:
tail = prev
# 查剩下的部分是否大于等于k
for i in range(k):
tail = tail.next
if not tail:
return dummy.next
k_next = tail.next
# 把子链表重新接回去
head,tail = self.reverse(head,tail)
prev.next = head
tail.next = k_next
prev = tail
head = tail.next
return dummy.next
23. 合并K个升序链表（最小堆）
题目链接：23. 合并K个升序链表
题目大意：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
例如：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
解题思路： 最小堆处理升序问题。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# 方法一： 把所有的数字取出来放最小堆里面，再重新建立链表
if not lists or len(lists) == 0: return None
import heapq
heap = []
# 去除所有元素
for node in lists:
while node:
heapq.heappush(heap,node.val)
node = node.next
# 建立新的链表
dummy = ListNode(-1)
cur = dummy
# 依次取出建立新的链表
while heap:
temp_node = ListNode(heapq.heappop(heap))
cur.next = temp_node
cur = cur.next
return dummy.next
1171. 从链表中删去总和值为零的连续节点（字典）
题目链接：1171. 从链表中删去总和值为零的连续节点
题目大意：给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
例如：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
解题思路 ：字典 也就是 哈希表 来找子数组为0.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0,head)
dic = {}
s = 0
cur = dummy
while cur:
s += cur.val
dic[s] = cur
cur = cur.next
# print(dic)
s = 0
cur = dummy
while cur:
s += cur.val
print(s)
cur.next = dic[s].next
cur = cur.next
return dummy.next
817. 链表组件（字符串函数调用）
题目链接：817. 链表组件
题目大意：给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。
例如：
输入: head = [0,1,2,3,4], nums = [0,3,1,4]
输出: 2
解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2
解题思路： 这个函数好用 对于这道题非常的有用。
getattr(object, name[, default])
Return the value of the named attribute of object. name must be a string.
If the string is the name of one of the object’s attributes, the result is the value of that attribute.
For example, getattr(x, 'foobar') is equivalent to x.foobar.
If the named attribute does not exist, default is returned if provided, otherwise AttributeError is raised.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def numComponents(self, head: Optional[ListNode], nums: List[int]) -> int:
nums = set(nums)
cur,ans = head,0
while cur:
if cur.val in nums and \
getattr(cur.next,'val',None) not in nums:
ans += 1
cur = cur.next
return ans
1019. 链表中的下一个更大节点（最小栈）
题目链接：1019. 链表中的下一个更大节点
题目大意：给定一个长度为 n 的链表 head。对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。
例如：
输入：head = [2,7,4,3,5]
输出：[7,0,5,5,0]
解题思路： 最小堆 可以快读定位下一个要链接的元素结点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def nextLargerNodes(self, head: Optional[ListNode]) -> List[int]:
tmp = []
while head:
tmp.append(head.val)
head = head.next
st,n = [],len(tmp)
ans = [0] * n
for i in range(n):
while st and tmp[st[-1]] < tmp[i]:
ans[st[-1]] = tmp[i]
st.pop()
st.append(i)
return ans
总结
??链表这一块的内容 做完了 还是有些，怎么说，比较散乱的认知，不过最基本的几个操作 也就是 上篇的内容必须了然于心，后续的综合或提升题就是各种基本操作的组合以及其他比较难理解的数据机构的结合，总之多思考，多学习，多练多总结。