给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
# 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:
if head == None or head.next == None:
# 临界条件,当head是空节点或者下一个节点为空时
return head
newHead = self.reverseList(head.next) # 处理子问题(子链表),并返回新的头节点
# 反转head和head的下一个节点,即head和子链表的尾节点
head.next.next = head
head.next = None
return newHead
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
# 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]:
if list1 == None:
return list2
if list2 == None:
return list1 # 临界条件
# 递推公式,比较当前两个链表头节点的值,较小的节点作为函数返回的头节点,并处理该头节点以后的部分和另一条完整的链表
if list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list2.next, list1)
return list2
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
# 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 head == None or head.next == None: # 临界条件
return head
head.next = self.deleteDuplicates(head.next)
return head.next if head.val == head.next.val else head
参考:CS-Notes