【Leetcode】链表——全题解
2020-08-07 本文已影响0人
李白开水
当前Leetcode的链表标签题目一共53道题，除了会员题目，题解基本都在这了，还可能陆续更新一题多解~
简单
（1）删除节点
面试题 02.03. 删除中间节点
同
237. 删除链表中的节点
- 如果当前节点有下一个节点，下一个节点也有下一个节点，那么把当前这个节点的值变为下一个节点的值，当前节点直接指向下一个节点的下一个节点（相当于删除的不是当前节点，而是把当前节点变成它下一个节点，把它下一个节点删除）
- 如果当前节点有下一个节点，但是下一个节点没有下一个节点了（当前节点是链表的倒数第二个节点），那么把当前节点的值变成下一个节点的值，当前节点指向None（还是相当于删除了下一个节点）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
if node.next:
if node.next.next:
node.val = node.next.val
node.next = node.next.next
else:
node.val = node.next.val
node.next = None
# 这一行有没有都可以通过，因为当前节点不为最后一个节点，而且不要求返回
return None
-------------------------------------------------------------------------------------------------
# 也可以：
if node.next:
node.val = node.next.val
if node.next.next:
node.next = node.next.next
else:
node.next = None
面试题 02.01. 移除重复节点
同
83. 删除排序链表中的重复元素
- 用字典保存节点的值，新建一个链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
mydict = {}
newhead = ListNode(0)
n = newhead
h = head
while h:
if h.val not in mydict:
mydict[h.val] = True
n.next = ListNode(h.val)
n = n.next
h = h.next
return newhead.next
原地：
- 新建节点作为新的头节点，它的next为head
- 使用两个指针一个字典
- 第一个指针指向新的头节点，第二个节点往下遍历，当遇到有新的值的节点，把第一个节点的next指向这个节点，把第一个节点指向这个节点，把这个节点的值加到字典中，第二个节点继续往下遍历
- 如果第二个指针遇到当前节点的值已经在字典中了，继续往下遍历
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeDuplicateNodes(self, head: ListNode) -> ListNode:
mydict = {}
newhead = ListNode(0)
newhead.next = head
cur = newhead
nex = cur.next
while nex:
if nex.val not in mydict:
cur.next = nex
mydict[nex.val] = True
cur = cur.next
nex = nex.next
cur.next = None
return newhead.next
203. 移除链表元素
- 同样的方法，题目稍有不同：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
newhead = ListNode(0)
newhead.next = head
cur = newhead
nex = cur.next
while nex:
if nex.val != val:
cur.next = nex
cur = cur.next
nex = nex.next
cur.next = None
return newhead.next
剑指 Offer 18. 删除链表的节点
- 和上面一样。。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, head: ListNode, val: int) -> ListNode:
newhead = ListNode(0)
newhead.next = head
cur, nex = newhead, newhead.next
while nex:
if nex.val != val:
cur.next = nex
cur = cur.next
nex = nex.next
cur.next = None
return newhead.next
（2）反转链表
206. 反转链表
同
剑指 Offer 24. 反转链表
image.png
把第一个节点指向newhead
image.png
newhead指向cur
image.png
cur指向nex
image.png
nex指向它的下一个
image.png
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head:
return None
newhead = None
cur = head
nex = cur.next
while cur:
cur.next = newhead
newhead = cur
cur = nex
if nex:
nex = nex.next
return newhead
（3）双指针：中间节点、环形链表
876. 链表的中间结点
- 定义一个快指针一个慢指针，快指针每次走两步，慢指针每次走一步，当快指针到链表的尾时，慢指针所在的位置就是链表的中间节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
fast = head
slow = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
剑指 Offer 22. 链表中倒数第k个节点
- 双指针，一个快指针，一个慢指针
- 快指针先走k步，走完k步之后，再和慢指针一起，每次走一步，当快指针到达链表的尾时，慢指针所在的位置就是要返回的倒数第k个节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if not head:
return None
fast = head
slow = head
while k > 0:
fast = fast.next
k -= 1
while fast:
fast = fast.next
slow = slow.next
return slow
面试题 02.02. 返回倒数第 k 个节点
- 与上一题稍有不同，返回的是节点的值
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
if not head:
return None
fast, slow = head, head
while k > 0:
fast = fast.next
k -= 1
while fast:
fast = fast.next
slow = slow.next
return slow.val
环形链表：
141. 环形链表
- 一个快指针一个慢指针，快指针每次走两步，慢指针每次走一步，如果快指针和慢指针走着走着相遇了，说明有环，返回True，否则返回False
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
两个链表
21. 合并两个有序链表
- 如果两个链表中有一个为空，直接返回另一个链表即可（如果两个都为空，那么返回其中哪一个都是返回一个空链表）
- 定义一个newhead，定义一个指针cur指向newhead
- 两个指针，一个指向l1的头，一个指向l2的头，比较当这两个指针都不为空时，比较这两个指针指向的节点的值，把较小的赋给cur，然后继续遍历
- 当这两个指针中有一个为空了，把不为空的那个指针指向的节点以及它以后的节点赋给cur
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2:
return l2 or l1
tmp1, tmp2 = l1, l2
newhead = ListNode(0)
cur = newhead
while tmp1 and tmp2:
if tmp1.val > tmp2.val:
cur.next = tmp2
tmp2 = tmp2.next
else:
cur.next = tmp1
tmp1 = tmp1.next
cur = cur.next
if tmp1:
cur.next = tmp1
else:
cur.next = tmp2
return newhead.next
（4）反转链表和双指针
234. 回文链表
同
面试题 02.06. 回文链表
- 先用双指针找到链表的中间节点，把从它的这个节点开始以后的节点组成的链表（也就是整个链表的后半部分）反转
- 双指针：一个快指针一个慢指针，慢指针每次走一步，快指针每次走两步，当快指针到达结尾的时候，慢指针所在的位置就是中间节点。要注意快指针的边界，当快指针的不是None，而且快指针的下一个也不是None才可以继续往下走。
- 比较前半部分和反转后的后半部分，这两个链表中只要有一个链表遍历到结尾就可以结束遍历，因为不管这个链表的节点是奇数个还是偶数个，都可以是一个回文链表
也就是例如 1——>2——>3——>2——>1，分成两个链表分别是1——>2和1——>2——>3比较，只要1，2相同即可。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head:
return True
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
newhead = None
cur = slow
nex = cur.next
while cur:
cur.next = newhead
newhead = cur
cur = nex
if nex:
nex = nex.next
h = head
while h and newhead:
if h.val == newhead.val:
h = h.next
newhead = newhead.next
else:
return False
return True
（5）双指针解决两个链表相交问题
160. 相交链表
同
剑指 Offer 52. 两个链表的第一个公共节点
同
面试题 02.07. 链表相交
- 两个指针，一个指针A从链表A的头开始走，另外一个指针B，从链表B的头开始走，当A或B走完自己的链表时，继续走对方的链表，如果指针A和指针B相遇了，返回指针A（这时候的返回有两种情况，一是有环的情况，AB相遇的位置是两个链表的第一个公共节点，二是没有环的情况，这时候返回的是None，因为AB都同时走了一样的路程：链表A和B，到达了终点相遇）
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
tmpA, tmpB = headA, headB
while tmpA != tmpB:
if tmpA:
tmpA = tmpA.next
else:
tmpA = headB
if tmpB:
tmpB = tmpB.next
else:
tmpB = headA
return tmpA
（6）其他
剑指 Offer 06. 从尾到头打印链表
- 遍历，把节点的值存在列表中，返回列表的逆序即可
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reversePrint(self, head: ListNode) -> List[int]:
res = []
h = head
while h:
res.append(h.val)
h = h.next
return res[::-1]
1290. 二进制链表转整数
举例：
如果输入是[1,0,0,1,0]，它的十进制树应该是18.
image.png
那么二进制转成十进制是这么算的：
image.png
定义一个res用来返回结果，每当遍历到一个新的节点，就把前面res的值*2再加上当前节点的值：
image.png
这样第一个1一共乘了四个2，第二个1一共乘了一个2，加在一起正好是返回的结果。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
res = 0
cur = head
while cur:
res = res * 2 + cur.val
cur = cur.next
return res
中等
（1）删除节点
82. 删除排序链表中的重复元素 II
- 时间复杂度是O(n)，空间复杂度小于O（n）
- 用一个字典来保存每一个节点的值出现了多少次
- 利用双指针删除节点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
mydict = {}
cur = head
newhead = ListNode(0)
newhead.next = head
while cur:
if cur.val in mydict:
mydict[cur.val] += 1
else:
mydict[cur.val] = 1
cur = cur.next
cur = newhead
nex = cur.next
while nex:
if mydict[nex.val] == 1:
cur.next = nex
cur = cur.next
nex = nex.next
cur.next = None
return newhead.next
因为是排序链表，还可以使用三指针：
参考：
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/chao-qing-xi-tu-jie-san-zhi-zhen-fa-by-justdo1t/
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
newhead = ListNode(0)
newhead.next = head
cur, left, right = newhead, newhead.next, newhead.next
while right:
while right.next and right.next.val == right.val:
right = right.next
if right == left:
cur.next = left
cur = cur.next
left = right.next
right = left
cur.next = None
return newhead.next
19. 删除链表的倒数第N个节点
- 双指针
- 因为被删除的节点至少是“倒数第一个”节点，所以如果链表本身就为空，那就直接返回空，链表本身只有一个节点，一定会删除倒数第一个节点，所以也返回空
- 快指针先走n个节点，如果这时fast为空，说明fast正好走完了链表，那么n既链表节点数，也就是长度为n的链表，删除倒数第n个节点，也就是删除第一个节点，这时直接返回head.next
- 如果fast先走n步，走完fast不为空，那么fast和slow一起继续走，并且循环while的条件是fast与fast.next都不为空，也就是fast最远走到最后一个节点
- 因为fast比slow走得快，所以可以保证slow.next一定存在，当fast走到最后一个节点，此时slow所在的位置就是被删除节点的前一个节点，此时只要将slow.next指向slow.next.next，因为slow.next一定存在（如上述），所以slow.next指向slow.next.next不会报错
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
if not head or not head.next:
return None
slow, fast = head, head
while n > 0:
fast = fast.next
n -= 1
if not fast:
return head.next
while fast and fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
（2）变换链表
24. 两两交换链表中的节点
- 三个指针
- 新建个头节点newhead，newhead的next指向head
- 用四个指针，cur，cur1，cur2，nex
- cur初始指向newhead，cur1指向head的第一个节点，cur2指向head的第二个节点，nex指向第三个
- 把cur的next指向cur2，cur2的next指向cur1，cur1的next指向None，就完成了两个节点的翻转
- 然后把cur1指向nex，cur2指向cur1的next，nex指向cur2的next
- 注意退出循环的条件
- 退出循环后，如果cur1还指向某个节点，要把这个节点加到链表的尾部
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
cur1, cur2 = head, head.next
nex = cur2.next
newhead = ListNode(0)
newhead.next = head
cur = newhead
while cur1 and cur2:
cur.next = cur2
cur2.next = cur1
cur = cur1
cur.next = None
cur1 = nex
if cur1 and cur1.next:
cur2 = cur1.next
else:
break
nex = cur2.next
if cur1:
cur.next = cur1
return newhead.next
61. 旋转链表
- 先遍历一遍链表计算链表的长度
- 把k和长度取余，然后使用快慢指针找到要旋转的节点，拼接一下即可
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if k == 0 or not head:
return head
lenth = 0
h = head
while h:
lenth += 1
h = h.next
lenth = k % lenth
if lenth == 0:
return head
fast = head
slow = head
while lenth > 0:
fast = fast.next
lenth -= 1
pivot = fast
while fast and fast.next:
fast = fast.next
slow = slow.next
pivot = pivot.next
newhead = slow.next
slow.next = None
pivot.next = head
return newhead
148. 排序链表
- 归并，把每个节点都分成一个一个节点
- 再把两个两个排好序拼在一起
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
fast, slow = head.next, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
right_head = slow.next
slow.next = None
left, right = self.sortList(head), self.sortList(right_head)
return self.merge(left, right)
# 合并两个链表
def merge(self, head1, head2):
h1, h2 = head1, head2
newhead = ListNode(0)
cur = newhead
while h1 and h2:
if h1.val > h2.val:
cur.next = h2
h2 = h2.next
else:
cur.next = h1
h1 = h1.next
cur = cur.next
cur.next = h1 or h2
return newhead.next
86. 分隔链表
同
面试题 02.04. 分割链表
- 新建两个头节点，一个用来保存比x小的节点，另一个用来保存其他的节点
- 最后把这两个链表合并即可
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def partition(self, head: ListNode, x: int) -> ListNode:
before, after = ListNode(0), ListNode(0)
cur1, cur2 = before, after
h = head
while h:
if h.val < x:
cur1.next = h
cur1 = cur1.next
else:
cur2.next = h
cur2 = cur2.next
h = h.next
cur2.next = None
cur1.next = after.next
return before.next
92. 反转链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
newhead = ListNode(0)
newhead.next = head
pre = newhead
for _ in range(m - 1):
pre = pre.next
tmp_head = None
cur = pre.next
for _ in range(n - m + 1):
nex = cur.next
cur.next = tmp_head
tmp_head = cur
cur = nex
pre.next.next = cur
pre.next = tmp_head
return newhead.next
109. 有序链表转换二叉搜索树
- 遍历链表找到中点，中点的值作为一个根，这个节点的左节点是左半边链表的中点，右节点是这个点右半边链表的中点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
if not head:
return None
if not head.next:
return TreeNode(head.val)
fast, slow = head.next.next, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
root = TreeNode(slow.next.val)
root.right = self.sortedListToBST(slow.next.next)
slow.next = None
root.left = self.sortedListToBST(head)
return root
328. 奇偶链表
- 把head作为奇链表的头和尾
- 把head.next作为偶链表的头和尾
- 遍历链表，当奇偶链表的尾还有下一个元素，就继续遍历
-
初始情况如下
image.png
-
奇链表的尾的下一个节点总是偶节点，偶链表的尾的下一个节点总是奇节点，所以把奇链表的尾指向偶链表的尾的下一个节点，把奇链表的尾移到这个节点，再把偶链表的尾指向奇链表的尾的下一个节点，把偶链表的尾移到这个节点
image.png
image.png
image.png
image.png
-
当奇链表的尾的下一个和偶链表的尾的下一个都为空时，把奇链表的尾的下一个指向偶链表的头即可
image.png
# 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: ListNode) -> ListNode:
if not head or not head.next:
return head
odd_head = head
odd_tail = head
even_head = head.next
even_tail = head.next
while odd_tail.next and even_tail.next:
odd_tail.next = even_tail.next
odd_tail = odd_tail.next
even_tail.next = odd_tail.next
even_tail = even_tail.next
odd_tail.next = even_head
return odd_head
143. 重排链表
- 找到链表的中间节点，把后半部分反转
- 穿插合并前半条链表和后半条链表
# 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: ListNode) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head:
return head
# 找到链表的中间节点
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# 反转后半部分链表
cur = slow.next
slow.next = None
newhead = None
while cur:
nex = cur.next
cur.next = newhead
newhead = cur
cur = nex
cur1 = head
cur2 = newhead
while cur1 and cur2:
nex1 = cur1.next
nex2 = cur2.next
cur1.next = cur2
cur1 = nex1
cur2.next = cur1
cur2 = nex2
return head
725. 分隔链表
- 先计算一下链表长度，如果链表长度大于等于要分割的块数，如用链表长度除以要分割多少块，求得每个子链表都需要有多少个节点partlen。再计算如果每块都有partlen个节点，最后还剩多少节点extra，多出来的这些节点要加到每个子链表上，每个子链表加一个节点，加到extra剩余为0为止。
- 然后开始遍历分割链表，把每个子链表的头存到res结果集中，要把每个子链表的尾切割开
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
res = []
lenth, extra, part_len = 0, 0, 0
h = root
while h:
lenth += 1
h = h.next
if lenth >= k:
extra = lenth % k
part_len = lenth // k
else:
part_len = 1
cur, nex = root, root
while k > 0:
tmp_lenth = 0
k -= 1
tmp_lenth = part_len + (extra > 0)
extra = max(0, extra - 1)
res.append(nex)
while cur and tmp_lenth > 1:
tmp_lenth -= 1
cur = cur.next
if cur:
nex = cur.next
cur.next = None
cur = nex
return res
（3）环路检测
面试题 02.08. 环路检测
同
142. 环形链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
fast, slow = head, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
fast = head
while slow != fast:
fast = fast.next
slow = slow.next
return slow
return None
（4）求值
2. 两数相加
同
面试题 02.05. 链表求和
- 核心代码只有 while tmp1 and tmp2这一块，就是不断求和，注意进位
- 如果两个链表中有一个遍历完了，注意要把剩的那个列表继续遍历完
- 如果两个链表都遍历完了，还要注意最后是否还有进位
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
res, flag = 0, 0
tmp1, tmp2 = l1, l2
newhead = ListNode(0)
cur = newhead
while tmp1 and tmp2:
cur.next = ListNode((tmp1.val + tmp2.val + flag) % 10)
flag = (tmp1.val + tmp2.val + flag) // 10
cur = cur.next
tmp1, tmp2 = tmp1.next, tmp2.next
while tmp1:
cur.next = ListNode((tmp1.val + flag) % 10)
flag = (tmp1.val + flag) // 10
cur = cur.next
tmp1 = tmp1.next
while tmp2:
cur.next = ListNode((tmp2.val + flag) % 10)
flag = (tmp2.val + flag) // 10
cur = cur.next
tmp2 = tmp2.next
if flag > 0:
cur.next = ListNode(flag)
return newhead.next
445. 两数相加 II
- 可以把两个链表翻转，然后按照两数相加一的算法来做这道题目
- 使用栈（官方题解）：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
stack1, stack2 = [], []
cur = l1
while cur:
stack1.append(cur.val)
cur = cur.next
cur = l2
while cur:
stack2.append(cur.val)
cur = cur.next
flag = 0
newhead = None
while stack1 or stack2 or flag != 0 :
cur1, cur2 = 0, 0
if stack1:
cur1 = stack1.pop()
if stack2:
cur2 = stack2.pop()
tmp = cur1 + cur2 + flag
flag = tmp // 10
tmp %= 10
cur = ListNode(tmp)
cur.next = newhead
newhead = cur
return newhead
817. 链表组件
- 遍历列表把每个值放在字典中
- 遍历链表，如果当前的值存在在字典中，flag为0，说明当前节点是组件的第一个节点，res+1，如果当前值存在在字典中，flag为1，继续遍历，如果当前值不在字典中，继续遍历，把flag置为0
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def numComponents(self, head: ListNode, G: List[int]) -> int:
mydict = {}
for i in G:
if i not in mydict:
mydict[i] = True
cur = head
res = 0
flag = 0
while cur:
if cur.val in mydict and flag == 0:
res += 1
flag = 1
elif cur.val not in mydict:
flag = 0
cur = cur.next
return res
其他
1019. 链表中的下一个更大节点
- 用一个栈来保存当前未找到更大节点值的节点
- res用来保存返回的结果
- 如果遍历到当前节点的值比栈顶的节点值还小或相等，把当前这个节点和它的下标保存到栈中
- 如果遍历到当前节点的值比栈顶的节点值大，就while循环，把当前节点的值都保存到栈顶下标所在的res中去，然后把当前节点append到栈中
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def nextLargerNodes(self, head: ListNode) -> List[int]:
res, stack = [], []
index = 0
cur = head
while cur:
res.append(0)
while stack and cur.val > stack[-1][0].val:
node = stack.pop()
res[node[1]] = cur.val
stack.append([cur,index])
cur = cur.next
index += 1
return res
1367. 二叉树中的列表
- 官方题解：递归
- 两个函数，一个用来向下递归找到head的值与节点值相等的节点
- 另一个函数用来找当前的相等节点的下一个节点和head.next的值是否相等
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
if not root:
return False
return self.helper(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
def helper(self, head, root):
if not head:
return True
if not root:
return False
if head.val != root.val:
return False
return self.helper(head.next, root.left) or self.helper(head.next, root.right)
1171. 从链表中删去总和值为零的连续节点
- 定义一个字典，遍历两次链表
- 遍历的时候维护一个sum
- 第一次遍历的时候，sum每遇到一个节点就加上这个节点的值，然后把sum作为key，当前的节点作为value保存在字典中，这样相同sum的结点，在前面出现的就会被后面出现的覆盖掉
-
第二次遍历的时候，依然维护这个sum，当前节点的下一个节点就是字典中sum对应的节点的下一个节点
第一次遍历：
image.png
第二次遍历：
image.png
image.png
image.png
image.png
image.png
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
mydict = {}
mysum = 0
newhead = ListNode(0)
cur = newhead
newhead.next = head
while cur:
mysum += cur.val
mydict[mysum] = cur
cur = cur.next
mysum = 0
cur = newhead
while cur:
mysum += cur.val
cur.next = mydict[mysum].next
cur = cur.next
return newhead.next
138. 复制带随机指针的链表
同
剑指 Offer 35. 复杂链表的复制
- 使用字典+遍历
- 第一次遍历：使用字典node_to_index，遍历链表，num由0开始，目的是把原来链表的每个节点作为key，num作为value保存在字典中。
- 例如[[7,null],[13,0],[11,4],[10,2],[1,0]]
-
字典中存储的是：{[节点“7”：0],[节点“13”：1],[节点“11”：2],[节点“10”：3],[节点“1”：4]}
image.png
-
第二次遍历：这次每个节点的index我们都知道了，第二次用字典index_to_random_index，把每个节点的index作为key，把这个节点的random的index作为value，保存在index_to_random_index字典中，random节点可以访问到，就可以用这个节点在第一次遍历得到的字典中取到这个random节点的index
image.png
- 第三次遍历：同时遍历原来的链表和新建一个新的头节点，用原来链表的值建一个新的链表。
-
第四次遍历：新建一个字典index_to_newnode，把节点的下标作为key，节点作为value保存到数组中。
image.png
-
第五次遍历：把新链表的每个节点的random添加进去，因为知道当前节点的下标，知道每个下标对应的random的下标，也知道每个下标对应的新链表的节点
image.png
image.png
image.png
image.png
image.png
- 代码实现的时候，有些循环合并了，所以只循环了三次：
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
newhead = Node(0)
cur = newhead
tmp = head
num = 0
mydict_node_to_index = {}
index_to_mynewnode = {}
while tmp:
cur.next = Node(tmp.val)
cur = cur.next
mydict_node_to_index[tmp] = num
index_to_mynewnode[num] = cur
num += 1
tmp = tmp.next
index_to_random_index = {}
tmp = head
while tmp:
index_to_random_index[mydict_node_to_index[tmp]] = None if not tmp.random else mydict_node_to_index[tmp.random]
tmp = tmp.next
cur = newhead.next
num = 0
while cur:
if index_to_random_index[num] is not None:
cur.random = index_to_mynewnode[index_to_random_index[num]]
cur = cur.next
num += 1
return newhead.next
一样的写法：
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
if not head:
return None
newhead = Node(0)
cur = newhead
tmp = head
node_to_index = {}
index_to_newhead = {}
num = 0
while tmp:
cur.next = Node(tmp.val)
cur = cur.next
index_to_newhead[num] = cur
node_to_index[tmp] = num
num += 1
tmp = tmp.next
index_to_random_index = {}
num = 0
tmp = head
while tmp:
index_to_random_index[num] = node_to_index[tmp.random] if tmp.random is not None else None
tmp = tmp.next
num += 1
cur = newhead.next
num = 0
while cur:
if index_to_random_index[num] is not None:
cur.random = index_to_newhead[index_to_random_index[num]]
cur = cur.next
num += 1
return newhead.next
430. 扁平化多级双向链表
具体实现看代码吧。
注意1是要把原来的child置为空，2是prev要有指向。
要是写完发现节点的顺序是对的，但是不是一个有效的双向链表估计就是注意1和2的问题，用循环打印一下当前节点的值和当前节点的prev值看看是不是有没连上的。
"""
# Definition for a Node.
class Node:
def __init__(self, val, prev, next, child):
self.val = val
self.prev = prev
self.next = next
self.child = child
"""
class Solution:
def flatten(self, head: 'Node') -> 'Node':
if not head:
return head
cur = head
while cur:
if cur.child:
self.helper(cur)
cur = cur.next
return head
def helper(self, node):
right = node.next
node.next = node.child
node.child.prev = node
node.child = None
while node.next:
if node.child:
self.helper(node)
node = node.next
node.next = right
if right:
right.prev = node
return node
147. 对链表进行插入排序
- 新建头节点
- 维护一个tail，一开始指向新的头节点
- 遍历链表，如果当前的节点比tail节点的值大，直接插在tail节点后，把tial指向这个新插入的节点，记得tail的next要指向空，要不就无限循环了。。
- 如果当前节点值比tail小，那么新建一个tmp指向头，找到当前节点应该插入的为止，把它插进去
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
newhead = ListNode(float('-inf'))
tail = newhead
cur = head
nex = cur
while cur:
nex = nex.next
if cur.val < tail.val:
tmp = newhead
while cur.val > tmp.val and cur.val > tmp.next.val:
tmp = tmp.next
cur.next = tmp.next
tmp.next = cur
else:
tail.next = cur
tail = tail.next
tail.next = None
cur = nex
return newhead.next
困难
23. 合并K个排序链表
解法一：
- 用小根堆把所有节点的值都保存起来，然后用这些值重新建一个新链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
heap = []
for i in lists:
while i:
heapq.heappush(heap,i.val)
i = i.next
head = ListNode(0)
cur = head
while heap:
cur.next = ListNode(heap[0])
heapq.heappop(heap)
cur = cur.next
return head.next
其他解法待更新~
25. K 个一组翻转链表
- 用pre来标志之前已经翻转过的链表尾
- cur表示当前要遍历的节点
- 定义一个newhead做新的链表头节点，把head赋给newhead的next
- 然后开始遍历，每到一个新的cur，把tail指向这个cur，然后tail向下遍历，找到要翻转的子链表的尾
- 使用helper函数，把cur和tail传给这个函数
- helper函数的实现：
- 把tail的next作为pre保存起来
- 当tail和pre不相同时，遍历继续
- 遍历的内容是从传递过来的cur开始把cur传给tmp，把tmp的next作为nex保存起来，再把tmp的next指向pre，这样就完成了一个节点的翻转，然后把pre指向当前节点，tmp指向nex，nex指向tmp.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
newhead = ListNode(0)
newhead.next = head
pre = newhead
cur = head
while cur:
tail = cur
for i in range(1, k):
tail = tail.next
if not tail:
return newhead.next
nex = tail.next
cur, tail = self.helper(cur, tail)
pre.next = cur
tail.next = nex
pre = tail
cur = tail.next
return newhead.next
def helper(self, head, tail):
pre = tail.next
tmp = head
while pre != tail:
nex = tmp.next
tmp.next = pre
pre = tmp
tmp = nex
return tail, head
