【Leetcode-3】
一、题目：两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
二、代码：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: last_v = 0 p1, p2 = l1, l2 head = p = ListNode(0) while p1 or p2 or last_v: v1 = p1.val if p1 else 0 v2 = p2.val if p2 else 0 v = v1 + v2 + last_v node = ListNode(v%10) last_v = v // 10 p.next = node p = p.next if p1: p1 = p1.next if p2: p2 = p2.next return head.next
【Leetcode-19】
一、题目：删除链表的倒数第n个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
二、代码：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: if not head: return head p = ListNode(0) p.next = head p1 = p2 = p for i in range(n): p2 = p2.next while p2 and p2.next: p1 = p1.next p2 = p2.next p1.next = p1.next.next return p.next
【Leetcode-21】
一、题目：合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
二、代码：
# 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: head = p = ListNode() p1, p2 = l1, l2 while p1 or p2: v1 = p1.val if p1 else float('inf') v2 = p2.val if p2 else float('inf') if v1 < v2: p.next = p1 p1 = p1.next else: p.next = p2 p2 = p2.next p = p.next return head.next
【Leetcode-23】
一、题目：合并k个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
二、代码：
# 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[ListNode]) -> ListNode: """ 分治思想，类似于归并排序 """ def split_and_merge(lists, l, r): if l == r: return lists[l] mid = (l + r) // 2 l1 = split_and_merge(lists, l, mid) l2 = split_and_merge(lists, mid+1, r) lt = merge_list(l1, l2) return lt def merge_list(l1, l2): dummy = ListNode() p1, p2, p = l1, l2, dummy while p1 or p2: val1 = p1.val if p1 else float('inf') val2 = p2.val if p2 else float('inf') if val1 < val2: p.next = p1 p1 = p1.next else: p.next = p2 p2 = p2.next p = p.next return dummy.next if not lists: return n = len(lists) l = split_and_merge(lists, 0, n-1) return l
【Leetcode-24】
一、题目：两两交换链表中的结点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
二、代码：
class Solution: def swapPairs(self, head: ListNode) -> ListNode: """ 每次走两步，交换2节点，若步数不到2则不交换 """ dummy = ListNode() dummy.next = head # 哑节点，避免处理头 p = dummy # p指向处理完成的节点 # 0-1-2-3..,p开始指向0 while p.next and p.next.next: tmp = p.next.next # tmp=2 p.next.next = tmp.next # 1-3 tmp.next = p.next # 2-1 p.next = tmp # 0-2 p = p.next.next return dummy.next
【Leetcode-25】
一、题目：K个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
二、代码：
def reverseKGroup(self, head: ListNode, k: int) -> ListNode: """ pre指向拼接完成链表的尾部，head和tail分别指向待翻转部分的头部和尾部，nxt指向未翻转部分的头部，如果没走k步就到了None，那么直接break """ def reverse(head): final_tail = head pre = None p = head while p: tmp = p.next p.next = pre pre = p p = tmp return pre, final_tail dummy = ListNode(0, head) pre, tail, head = dummy, dummy, dummy.next while pre: # 未翻转完 i = 0 while i < k: tail = tail.next if not tail: return dummy.next i += 1 # 断开再翻转 nxt = tail.next tail.next = None head, tail = reverse(head) # 接起来 pre.next = head tail.next = nxt pre = tail head = tail.next return dummy.next
【Leetcode-61】
一、题目：旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
二、代码：
def rotateRight(self, head: ListNode, k: int) -> ListNode: """ 链表长度n,移动k%n次 移动方法：把链表连成环，起始在head，然后在后移n-k-1处切开 1->2->3->4->5，k=1则移动5-1-1=3次，到4，4处切开，返回5处 """ if not head or not head.next or k == 0: return head # 计算链表长度 n = 1 p = head while p.next: n += 1 p = p.next if n <= 1 or k % n == 0: # 不必移动 return head k = k % n # 连成环 p.next = head p = head k = n - k - 1 # 在此后面断开 while k > 0: # k -= 1 p = p.next # 切开 h = p.next p.next = None return h
【Leetcode-82】
一、题目：删除排序链表中的重复元素2
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
二、代码：
def deleteDuplicates(self, head: ListNode) -> ListNode: """ pre指向已处理完的链表，判断pre.next是否是重复的，重复就循环删除 注意： 1.不重复直接往下走 2.重复的话pre不往下走，因为此刻只是走到了一个重复元素的下一个，这个元素不知道会不会重复，也是未处理，因此pre不变 """ dummy = ListNode(0, head) pre = dummy while pre: # 未处理完 if pre.next and pre.next.next and pre.next.val == pre.next.next.val: # 已经重复，删除这个元素,一直过了这个元素到下一位 p = pre.next val = p.val while p and p.val == val: p = p.next pre.next = p else: pre = pre.next return dummy.next
【Leetcode-86】
一、题目：分割链表
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
二、代码：
def partition(self, head: ListNode, x: int) -> ListNode: """ 慢指针p1指向<x的元素的尾部，快指针p2指向待处理的元素，遇到<x的元素则接到p1的后面,pre指向p2的前一个用于接链表 """ dummy = ListNode(0, head) p1, pre, p2 = dummy, dummy, head while p2: if p2.val < x: # 拆出来再插入 pre.next = p2.next p2.next = p1.next p1.next = p2 p1 = p1.next pre = p2 p2 = p2.next return dummy.next
【Leetcode-138】
一、题目：复制带随机指针的链表
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
二、代码：
""" # 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': """ 原结点后增加副本->补充副本的random->副本拆分出来 """ if not head: return head # 原结点后增加副本 p = head while p: node = Node(p.val) node.next = p.next p.next = node p = p.next.next # 补充副本的random p = head while p: p.next.random = p.random.next if p.random else None p = p.next.next # 副本拆分出来 p1 = head head2 = p2 = head.next while p2.next: p1.next = p2.next p2.next = p2.next.next p1 = p1.next p2 = p2.next return head2
【Leetcode-141】
一、题目：两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
二、代码：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def swapPairs(self, head: ListNode) -> ListNode: """ 每次走两步，交换2节点，若步数不到2则不交换 """ dummy = ListNode() dummy.next = head # 哑节点，避免处理头 p = dummy # p指向处理完成的节点 # 0-1-2-3..,p开始指向0 while p.next and p.next.next: tmp = p.next.next # tmp=2 p.next.next = tmp.next # 1-3 tmp.next = p.next # 2-1 p.next = tmp # 0-2 p = p.next.next return dummy.next
【Leetcode-141】
一、题目：环形链表
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 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: p1 = p2 = head while p2 and p2.next: p1 = p1.next p2 = p2.next.next if p1 == p2: return True return False
【Leetcode-142】
一、题目：环形链表2
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
二、代码：
class Solution: def detectCycle(self, head: ListNode) -> ListNode: p1 = p2 = head flag = False # 无环 while p2 and p2.next: p1 = p1.next p2 = p2.next.next if p1 == p2: flag = True # 有环 break if flag: p2 = head while p1 != p2: p1 = p1.next p2 = p2.next return p1 else: return None
【Leetcode-146】
一、题目：LRU缓存机制
二、代码：
class ListNode: def __init__(self, key=None, value=None): self.key = key self.value = value self.pre = None self.next = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.hashmap = {} self.head = ListNode() self.tail = ListNode() self.head.next = self.tail self.tail.pre = self.head def move_to_head(self, node): # 从原位置拆出来，放到开头 node.pre.next = node.next node.next.pre = node.pre self.insert_to_head(node) def insert_to_head(self, node): node.next = self.head.next self.head.next.pre = node node.pre = self.head self.head.next = node def get(self, key: int) -> int: if key in self.hashmap: node = self.hashmap[key] self.move_to_head(node) return node.value else: return -1 def put(self, key: int, value: int) -> None: if key in self.hashmap: self.hashmap[key].value = value node = self.hashmap[key] self.move_to_head(node) else: if len(self.hashmap) == self.capacity: # 在尾部删除一个节点 del_node = self.tail.pre del_node.pre.next = self.tail self.tail.pre = del_node.pre del self.hashmap[del_node.key] node = ListNode(key, value) self.hashmap[key] = node self.insert_to_head(node) # Your LRUCache object will be instantiated and called as such: # obj = LRUCache(capacity) # param_1 = obj.get(key) # obj.put(key,value)
【Leetcode-148】
一、题目：排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
二、代码：
# 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: ListNode) -> ListNode: def my_sort(root): # 在中间拆分 if not root or not root.next: return root p1, p2 = root, root.next while p2 and p2.next: p1 = p1.next p2 = p2.next.next # 截断 left = root right = p1.next p1.next = None # 分别排序 left = my_sort(left) right = my_sort(right) # 合并 pre = p = ListNode(0) p1, p2 = left, right while p1 or p2: v1 = p1.val if p1 else float('inf') v2 = p2.val if p2 else float('inf') if v1 < v2: p.next = p1 p1 = p1.next else: p.next = p2 p2 = p2.next p = p.next return pre.next root = my_sort(head) return root
【Leetcode-160】
一、题目：相交链表
编写一个程序，找到两个单链表相交的起始节点。
二、代码：
# 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: p1, p2 = headA, headB while p1 or p2: if p1 == p2: break p1 = p1.next if p1 else headB p2 = p2.next if p2 else headA return p1
【Leetcode-206】
一、题目：反转链表
反转一个单链表。
二、代码：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: ListNode) -> ListNode: pre = None p = head while p: tmp = p.next p.next = pre pre = p p = tmp return pre