链表
链表结构
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例：
image
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
输入：head = [], val = 1
输出：[]
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
思路：我承认我偷懒了，但是在代码里直接注释说明，思路可能会更好一些~你说呢
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
res = ListNode() # 创建一个用于返回的Node
res.next = head # 使这个Node链接head
cur = res # 创建链表指针 假如创建 cur = res.next 这样会导致链表第一个元素没有判断 当然这个问题也可以在while循环中解决
while cur: # 当前节点存在
if cur.next and cur.next.val == val: # 为什么要直接判断cur.next呢，这样可以防止链表的最后一个元素没有被判断
cur.next = cur.next.next
else:
cur = cur.next
return res.next
旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例：
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]
输入：head = [0,1,2], k = 4
输出：[2,0,1]
提示：
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109
通过次数223,034提交次数
思路：
- 求链表长度
- 找出倒数第k+1个节点
- 链表重构
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 链表为空或者链表只有一个元素，直接返回头节点
if not head or not head.next:
return head
# 获得链表长度, 注意为真实长度，从1计数
len_ = 0
cur = head
while cur:
len_ += 1
cur = cur.next
# 获得余数
k %= len_
# 如果k==0，代表不需要旋转链表
if k == 0:
return head
# 快慢指针 当k=0时，quick指向k+1的节点
quick, slow = head, head
while k:
quick = quick.next
k -= 1
# 当循环结束时，quick指向最后一个节点，slow指向倒数第k+1个节点
while quick.next:
quick = quick.next
slow = slow.next
# 设置新的头节点
newHead = slow.next
# 断开链表
slow.next = None
# 链接前半段与后半段
quick.next = head
return newHead
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
输入：l1 = [], l2 = []
输出：[]
输入：l1 = [], l2 = [0]
输出：[0]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
思路：归并排序的思路，两个指针哪个小就添加哪个，同时挪动指针
# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
res = ListNode()
cur, p1, p2 = res, list1, list2
while p1 and p2:
if p1.val < p2.val:
cur.next = p1
p1 = p1.next
else:
cur.next = p2
p2 = p2.next
cur = cur.next
cur.next = p1 or p2
return res.next
删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例:
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
输入：head = [1,1,1,2,3]
输出：[2,3]
提示:
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
思路:只有要相同的节点就全部删除,代码如下:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head:
return head
dummy = ListNode(0, head)
cur = dummy
while cur.next and cur.next.next:
if cur.next.val == cur.next.next.val:
x = cur.next.val
while cur.next and cur.next.val == x:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
