网站建设后期需要后期做的,wordpress options framework,广告主资源哪里找,常州网站建设公司效果LeetCode:高频链表题目总结 问题描述#xff1a;
LeetCode: 2. 两数相加 , 注意是逆序存储#xff0c;相加求和LeetCode: 19. 删除链表的倒数第 N 个结点LeetCode: 21. 合并两个有序链表LeetCode: 23. 合并 K 个升序链表LeetCode: 24. 两两交换链表中的节点 #xff0c;两… LeetCode:高频链表题目总结 问题描述
LeetCode: 2. 两数相加 , 注意是逆序存储相加求和LeetCode: 19. 删除链表的倒数第 N 个结点LeetCode: 21. 合并两个有序链表LeetCode: 23. 合并 K 个升序链表LeetCode: 24. 两两交换链表中的节点 两两相邻的节点交换LeetCode: 25. K 个一组翻转链表LeetCode: 61. 旋转链表LeetCode: 83. 删除排序链表中的重复元素 已经排序只保留一个LeetCode: 82. 删除排序链表中的重复元素 II 已经排序一个不保留LeetCode: 86. 分隔链表 根据一个元素判断小的在前面大的在后面LeetCode: 92. 反转链表 II 给定一个区间[left right]进行反转LeetCode: 114. 二叉树展开为链表 先序遍历类型LeetCode: 138. 复制带随机指针的链表LeetCode: 141. 环形链表 判断是否存在环LeetCode: 142. 环形链表 II 找环的入口LeetCode: 143. 重排链表 首尾交替链接类型LeetCode: 148. 排序链表 由小到大排序归并排序即可LeetCode: 160. 相交链表 求两个链表的交点LeetCode: 206. 反转链表 头插发LeetCode: 234. 回文链表 输出反转剑指 Offer 18. 删除链表的节点 正常删除类型剑指 Offer 22. 链表中倒数第k个节点 查找类型
1LeetCode: 2. 两数相加 Python3实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]:carry 0notehead ListNode(0)curr noteheadwhile l1 ! None or l2 ! None:n l1.val if l1 ! None else 0m l2.val if l2 ! None else 0sum carry n mcarry int(sum/10)curr.next ListNode(sum%10)curr curr.nextif l1 ! None: l1 l1.next # 进入下一个if l2 ! None: l2 l2.next if carry 0:curr.next ListNode(carry)return notehead.next2LeetCode: 19. 删除链表的倒数第 N 个结点 Python3实现
class Solution:def removeNthFromEnd(self, head: Optional[ListNode], n: int) - Optional[ListNode]:res ListNode(0, head)fist headsecond resfor _ in range(n):fist fist.nextwhile fist:fist fist.nextsecond second.nextsecond.next second.next.nextreturn res.next3LeetCode: 21. 合并两个有序链表 Python3实现
class Solution:def mergeTwoLists(self, list1, list2):if not list1: return list2if not list2: return list1if list1.val list2.val:l3, list1 list1, list1.nextelse:l3, list2 list2, list2.nextcur l3while list1 and list2:if list1.val list2.val:cur.next, list1 list1, list1.nextelse:cur.next, list2 list2, list2.nextcur cur.nextcur.next list1 if list1 else list2return l34LeetCode: 23. 合并 K 个升序链表 Python3实现
class Solution:def mergeTwoLists(self, list1, list2):if not list1: return list2if not list2: return list1if list1.val list2.val: l3, list1 list1, list1.nextelse:l3, list2 list2, list2.nextcur l3while list1 and list2:if list1.val list2.val: cur.next, list1 list1, list1.nextelse: cur.next, list2 list2, list2.nextcur cur.nextcur.next list1 if list1 else list2return l3def mergeKLists(self, lists):if len(lists) 0:return Noneif len(lists) 1:return lists[0]k len(lists)res lists[0]for i in range(1, k):res self.mergeTwoLists(res, lists[i])return res5LeetCode: 24. 两两交换链表中的节点 Python3实现
class Solution:def swapPairs(self, head):if not head: return headres ListNode(0, head)c reswhile c.next and c.next.next:a, b c.next, c.next.nextc.next, a.next b, b.nextb.next ac c.next.nextreturn res.next6LeetCode: 25. K 个一组翻转链表 Python3实现
class Solution:# 翻转一个子链表并且返回新的头与尾def reverse(self, head: ListNode, tail: ListNode):prev tail.nextp headwhile prev ! tail:nex p.nextp.next prevprev pp nexreturn tail, headdef reverseKGroup(self, head: ListNode, k: int) - ListNode:hair ListNode(0)hair.next headpre hairwhile head:tail pre# 查看剩余部分长度是否大于等于 kfor i in range(k):tail tail.nextif not tail:return hair.nextnex tail.nexthead, tail self.reverse(head, tail)# 把子链表重新接回原链表pre.next headtail.next nexpre tailhead tail.nextreturn hair.next7LeetCode: 61. 旋转链表 Python3实现
class Solution:def rotateRight(self, head: Optional[ListNode], k: int) - Optional[ListNode]:if k 0 or not head or not head.next:return headcur headn 1while cur.next:cur cur.nextn 1add n - k % n if add n: # 倍数的时候return headcur.next headwhile add:cur cur.nextadd - 1res cur.nextcur.next Nonereturn res8LeetCode: 83. 删除排序链表中的重复元素 Python3实现
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:if not head:return headcur headwhile cur.next:if cur.next.val cur.val:cur.next cur.next.nextelse:cur cur.nextreturn head9LeetCode: 82. 删除排序链表中的重复元素 II Python3实现
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) - Optional[ListNode]:if not head:return headpre ListNode(0, head)cur prewhile cur.next and cur.next.next:if cur.next.val cur.next.next.val:x cur.next.valwhile cur.next and cur.next.val x:cur.next cur.next.nextelse:cur cur.nextreturn pre.next10LeetCode: 86. 分隔链表 Python3实现
class Solution:def partition(self, head: Optional[ListNode], x: int) - Optional[ListNode]:small ListNode()large ListNode()pre_small smallpre_large largewhile head:if head.val x:small.next headsmall small.nextelse:large.next headlarge large.nexthead head.nextlarge.next Nonesmall.next pre_large.nextreturn pre_small.next11LeetCode: 92. 反转链表 II Python3实现
class Solution:def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]:pre_head ListNode(0, head)pre pre_headfor _ in range(left -1):pre pre.nextcur pre.nextfor _ in range(right - left):tmp cur.nextcur.next cur.next.nexttmp.next pre.nextpre.next tmpreturn pre_head.next12LeetCode: 114. 二叉树展开为链表 Python3实现
class Solution:def flatten(self, root: Optional[TreeNode]) - None:Do not return anything, modify root in-place instead.res []def dfs(root):if root:res.append(root)if root.left: dfs(root.left)if root.right: dfs(root.right)dfs(root)n len(res)for i in range(1, n):pre, cur res[i-1], res[i]pre.left Nonepre.right cur13LeetCode: 138. 复制带随机指针的链表 Python3实现
class Solution:def copyRandomList(self, head: Optional[Node]) - Optional[Node]:my_dict {}def copynode(node):if node is None: return Noneif my_dict.get(node): return my_dict.get(node)root Node(node.val) # 存入字典my_dict[node] rootroot.next copynode(node.next) # 继续获取下一个节点root.random copynode(node.random) # 继续获取下一个随机节点return rootreturn copynode(head)14LeetCode: 141. 环形链表 Python3实现
class Solution:def hasCycle(self, head: ListNode) - bool:if not head or not head.next:return Falseslow headfast head.nextwhile slow ! fast:if not fast or not fast.next:return Falseslow slow.nextfast fast.next.nextreturn True15LeetCode: 142. 环形链表 II Python3实现
class Solution:def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]:slow headfast headwhile fast:slow slow.nextif not fast.next:return Nonefast fast.next.nextif fast slow:pre headwhile pre ! slow:slow slow.nextpre pre.nextreturn prereturn None16LeetCode: 143. 重排链表 Python3实现
class Solution:def reorderList(self, head):if not head: returnltmp []cur headwhile cur: # 转换成列表ltmp.append(cur)cur cur.nextn len(ltmp) # 链表长度for i in range(n // 2): # 处理ltmp[i].next ltmp[n - 1 - i]ltmp[n - 1 - i].next ltmp[i 1]ltmp[n // 2].next None # 最后一个指向空17LeetCode: 148. 排序链表 Python3实现
class Solution:def sortList(self, head: ListNode) - ListNode:if not head or not head.next:return headslow headfast headwhile fast.next and fast.next.next: # 用快慢指针分成两部分slow slow.nextfast fast.next.nextmid slow.next # 找到左右部分, 把左部分最后置空slow.next Noneleft self.sortList(head) # 递归下去right self.sortList(mid)return self.merge(left, right) # 合并def merge(self, left, right):dummy ListNode(0)p dummyl leftr rightwhile l and r:if l.val r.val:p.next ll l.nextp p.nextelse:p.next rr r.nextp p.nextif l:p.next lif r:p.next rreturn dummy.next18LeetCode: 160. 相交链表 Python3实现
class Solution:def getIntersectionNode(self, headA: ListNode, headB: ListNode) - Optional[ListNode]:if headA is None or headB is None:return Nonepa headApb headBwhile pa ! pb:pa pa.next if pa else headBpb pb.next if pb else headAreturn pa19LeetCode: 206. 反转链表 Python3实现
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:if not head: return headpre Nonecur headnext head.nextwhile next:cur.next prepre curcur nextnext next.nextcur.next prereturn cur20LeetCode: 234. 回文链表 Python3实现
class Solution:def isPalindrome(self, head: Optional[ListNode]) - bool:vals []cur headwhile cur:vals.append(cur.val)cur cur.nextreturn vals vals[::-1]21剑指 Offer 18. 删除链表的节点 Python3实现
class Solution:def deleteNode(self, head: ListNode, val: int) - ListNode:if head is None:return headpre ListNode(0)pre.next headcur prewhile cur and cur.next:if cur.next.val val:cur.next cur.next.nextcur cur.nextreturn pre.next22剑指 Offer 22. 链表中倒数第k个节点 Python3实现
class Solution:def getKthFromEnd(self, head: ListNode, k: int) - ListNode:res ListNode(0)res.next headfist headsecond resfor _ in range(k):fist fist.nextwhile fist:fist fist.nextsecond second.nextreturn second.next相关参考 声明 总结学习有问题或不当之处可以批评指正哦谢谢。
