1. 视频题目
1.1 反转链表
1.1.1 描述
给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2] 输出:[2,1]
示例 3:
输入:head = [] 输出:[]
提示:
链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
1.1.2 代码
新建另外一个带头结点的链表,然后使用头插法,新元素从头部插入
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
dummy = ListNode()
while head:
temp = head.next
head.next = dummy.next
dummy.next = head
head = temp
return dummy.next
1.1.3 总结
因为是反转链表,所以要用头插法
1.2 删除链表的倒数第 N 个结点
1.2.1 描述
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
示例 1:
输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1 输出:[]
示例 3:
输入:head = [1,2], n = 1 输出:[1]
提示:
链表中结点的数目为 sz 1 <= sz <= 30 0 <= Node.val <= 100 1 <= n <= sz
进阶:你能尝试使用一趟扫描实现吗?
1.2.2 代码
链表题目,先新建一个空的头结点,然后从这里开始。经验之谈,一般都挺好使
要删除倒数第n 个结点,就是搞出两个间隔为n 的双指针。注意,是间隔为n
一个到达最后结点,也就是.next==null ,另一个就是被删除结点的前一个结点
所以使得slow 指针指向slow.next.next ,即跳过被删除的slow.next 即可
然后发现这个方法对于边界条件如示例2 和3 都适用,直接给过
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = ListNode()
dummy.next = head
fast = dummy
while n>0 and fast:
fast = fast.next
n -= 1
slow = dummy
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.next
1.2.3 总结
本题再一次证明了,遇到链表题目先建一个新的头结点再说
然后就是,要删除链表的一个结点,一般是操作其前一个结点
还有就是,一定要注意间隔,这和长度不是一个概念,两者相差1
2. 作业题目
2.1 删除排序链表中的重复元素
2.1.1 描述
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
示例 1:
输入:head = [1,1,2] 输出:[1,2]
示例 2:
输入:head = [1,1,2,3,3] 输出:[1,2,3]
提示:
链表中节点数目在范围 [0, 300] 内 -100 <= Node.val <= 100 题目数据保证链表已经按升序 排列
2.1.2 代码
直接判断当前结点的下一个结点的值是否与当前结点的值相同
如果相同则跳过结点,即当前指针. 指向.next.next
需要注意的是条件的判断,当前指针不为空主要是防止链表为空
下一个结点不为空则是因为需要取下一个结点的值进行判断
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
dummy = ListNode()
dummy.next = head
while head and head.next:
if head.val == head.next.val :
head.next = head.next.next
else:
head = head.next
return dummy.next
2.1.3 总结
本题再一次证明了,遇到链表题目先建一个新的头结点再说
然后就是,要删除链表的一个结点,一般是操作其前一个结点
2.2 环形链表
2.2.1 描述
给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true 。 否则,返回 false 。
示例 1:
输入:head = [3,2,0,-4], pos = 1 输出:true 解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0 输出:true 解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1 输出:false 解释:链表中没有环。
提示:
链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个 有效索引 。
进阶:你能用 O(1)(即,常量)内存解决此问题吗?
2.2.2 代码
判断成环,经典的快慢指针问题,快指针每次走两步,慢指针一步
如果两者相遇则证明一定有环,但凡出现None 就证明无环且到尽头
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head and head.next:
fast = head.next.next
else:
fast = None
slow = head
while fast and slow and fast.next:
if fast != slow:
slow = slow.next
fast = fast.next.next
else:
return True
return False
2.2.3 总结
涉及到next 的问题一定要确保结点不为空,否则引用值无效
也就是说,我们需要确保引用.next 和.val 的那个结点不为空
尤其是当这个引用本身就包含其他引用,也就是.next.next 的情况
2.3 排序链表
2.3.1 描述
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
示例 1:
输入:head = [4,2,1,3] 输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5]
示例 3:
输入:head = [] 输出:[]
提示:
链表中节点的数目在范围 [0, 5 * 104] 内 -105 <= Node.val <= 105
进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
2.3.2 代码
刚开始看到 O(n log n) 我就想到了快排,然后感觉太复杂了,改用插入排序
然后就…超时了,题目上不是说O(n log n)是进阶吗?然后看题解发现这是题目要求…
按照这个时间复杂度限制的要求,考虑到链表不同于数组,题解给的是归并排序
那就是有划分与合并的两个步骤,划分就是单纯的划分就好,合并是合并两个有序链表
所以递归的跳出条件,就是最终划分出两个单个元素,然后在合并当中按大小排序
class Solution:
def sortList(self, head: ListNode) -> ListNode:
def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
if not head:
return head
if head.next == tail:
head.next = None
return head
slow = fast = head
while fast != tail:
slow = slow.next
fast = fast.next
if fast != tail:
fast = fast.next
mid = slow
return merge(sortFunc(head, mid), sortFunc(mid, tail))
def merge(head1: ListNode, head2: ListNode) -> ListNode:
dummyHead = ListNode(0)
temp, temp1, temp2 = dummyHead, head1, head2
while temp1 and temp2:
if temp1.val <= temp2.val:
temp.next = temp1
temp1 = temp1.next
else:
temp.next = temp2
temp2 = temp2.next
temp = temp.next
if temp1:
temp.next = temp1
elif temp2:
temp.next = temp2
return dummyHead.next
return sortFunc(head, None)
2.3.3 总结
归并排序有划分与合并的两个步骤,划分就是单纯的划分就好,合并是合并两个有序链表
所以递归的跳出条件,就是最终划分出两个单个元素,然后在合并当中按大小排序
|