赞
踩
【面试必刷TOP101】系列包含:
step 1:任意一个链表为空,返回另一个链表就行了,因为链表为空相当于 0,0 加任何数为 0,包括另一个加数为 0 的情况。
step 2:相继反转两个待相加的链表,反转过程可以参考 反转链表。
step 3:设置返回链表的链表头,设置进位
c
a
r
r
y
=
0
carry=0
carry=0。
step 4:从头开始遍历两个链表,直到两个链表节点都为空且
c
a
r
r
y
carry
carry 也不为 1。每次取出不为空的链表节点值,为空就设置为 0,将两个数字与
c
a
r
r
y
carry
carry 相加,然后查看是否进位,将进位后的结果(对 10 取模)加入新的链表节点,连接在返回链表后面,并继续往后遍历。
step 5:返回前将结果链表再反转回来。
class Solution:
def ReverseList(self, pHead: ListNode) -> ListNode:
if pHead == None:
return None
cur = pHead
pre = None
while cur != None:
temp = cur.next
cur.next = pre
pre = cur
cur = temp
return pre
def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
if head1 == None:
return head2
if head2 == None:
return head1
head1 = self.ReverseList(head1)
head2 = self.ReverseList(head2)
res = ListNode(-1)
head = res
carry = 0
while head1 != None or head2 != None or carry != 0:
val1 = 0 if head1 == None else head1.val
val2 = 0 if head2 == None else head2.val
temp = val1 + val2 + carry
carry = int(temp / 10)
temp = temp % 10
head.next = ListNode(temp)
head = head.next
if head1 != None:
head1 = head1.next
if head2 != None:
head2 = head2.next
return self.ReverseList(res.next)
时间复杂度:
O
(
m
a
x
(
m
,
n
)
)
O(max(m,n))
O(max(m,n)),其中
m
m
m 与
n
n
n 分别为两个链表的长度,翻转链表三次,复杂度分别是
O
(
n
)
O(n)
O(n)、
O
(
m
)
O(m)
O(m)、
O
(
m
a
x
(
m
,
n
)
)
O(max(m,n))
O(max(m,n)),相加过程也是遍历较长的链表。
空间复杂度:
O
(
1
)
O(1)
O(1),常数级指针,没有额外辅助空间,返回的新链表属于必要空间。
class Solution:
def merge(self, pHead1: ListNode, pHead2: ListNode) -> ListNode:
if pHead1 == None:
return pHead2
if pHead2 == None:
return pHead1
head = ListNode(-1)
cur = head
while pHead1 != None and pHead2 != None:
if pHead1.val <= pHead2.val:
cur.next = pHead1
pHead1 = pHead1.next
else:
cur.next = pHead2
pHead2 = pHead2.next
cur = cur.next
if pHead1 != None:
cur.next = pHead1
if pHead2 != None:
cur.next = pHead2
return head.next
def sortInList(self , head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
left = head
mid = head.next
right = head.next.next
while right != None and right.next != None:
left = left.next
mid = mid.next
right = right.next.next
left.next = None
return self.merge(self.sortInList(head),self.sortInList(mid))
时间复杂度:O(nlogn),归并排序的复杂度。
空间复杂度:O(logn),递归栈的深度最坏为 logn 层。
class Solution:
def sortInList(self , head: ListNode) -> ListNode:
a = []
p = head
while p != None:
a.append(p.val)
p = p.next
p = head
a = sorted(a)
for i in range(0,len(a)):
p.val = a[i]
p = p.next
return head
时间复杂度:O(nlogn),sort 函数的复杂度
空间复杂度:O(n),存储链表元素值的辅助数组长度 n
class Solution:
def isPail(self , head: ListNode) -> bool:
a = []
while head != None:
a.append(head.val)
head = head.next
b = a.copy()
b.reverse()
for i in range(0,len(a)):
if a[i] != b[i]:
return False
return True
时间复杂度:O(n),其中 n 为链表的长度,遍历链表转化数组为 O(n),反转数组为 O(n),后续遍历两个数组为 O(n)。
空间复杂度:O(n),记录链表元素的辅助数组。
class Solution:
def isPail(self , head: ListNode) -> bool:
a = []
while head != None:
a.append(head.val)
head = head.next
left = 0
right = len(a) - 1
while left <= right:
if a[left] != a[right]:
return False
left = left + 1
right = right - 1
return True
时间复杂度:O(n),其中 n 为链表的长度,遍历链表转化数组为 O(n),双指针遍历半个数组为 O(n)。
空间复杂度:O(n),记录链表元素的辅助数组。
class Solution:
def reverse(self, head: ListNode):
p = None
while head != None:
temp = head.next
head.next = p
p = head
head = temp
return p
def isPail(self , head: ListNode) -> bool:
p = head
n = 0
while p != None:
n = n + 1
p = p.next
n = n / 2
p = head
while n > 0:
p = p.next
n = n - 1
p = self.reverse(p)
q = head
while p != None:
if p.val != q.val:
return False
p = p.next
q = q.next
return True
时间复杂度:O(n),其中 n 为链表的长度,遍历链表找到长度为 O(n),后续反转链表为 O(n),然后再遍历两份半个链表。
空间复杂度:O(1),常数级变量,没有额外辅助空间。
class Solution:
def reverse(self, head: ListNode):
p = None
while head != None:
temp = head.next
head.next = p
p = head
head = temp
return p
def isPail(self , head: ListNode) -> bool:
if head == None:
return True
p = head
q = head
while p != None and p.next != None:
p = p.next.next
q = q.next
q = self.reverse(q)
p = head
while q != None:
if p.val != q.val:
return False
p = p.next
q = q.next
return True
时间复杂度:O(n),其中 n 为链表的长度,双指针找到中点遍历半个链表,后续反转链表为 O(n),然后再遍历两份半个链表。
空间复杂度:O(1),常数级变量,没有额外辅助空间。
class Solution:
def isPail(self , head: ListNode) -> bool:
p = head
a = []
while p:
a.append(p.val)
p = p.next
p = head
while len(a) != 0:
if p.val != a.pop():
return False
p = p.next
return True
时间复杂度:O(n),其中 n 为链表的长度,遍历链表入栈为 O(n),后续再次遍历链表和栈。
空间复杂度:O(n),记录链表元素的辅助栈。
class Solution:
def oddEvenList(self , head: ListNode) -> ListNode:
if head == None:
return head
p = head
q = head.next
res = q
while q != None and q.next != None:
p.next = q.next
p = p.next
q.next = q.next.next
q = q.next
p.next = res
return head
时间复杂度:O(n),遍历一次链表。
空间复杂度:O(1),常数个指针,无额外辅助空间。
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
if head == None:
return None
p = head
while p != None and p.next != None:
if p.val == p.next.val:
p.next = p.next.next
else:
p = p.next
return head
时间复杂度:O(n),其中 n 为链表长度,遍历一次链表。
空间复杂度:O(1),没有使用额外的辅助空间。
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
if head == None:
return None
res = ListNode(-1)
res.next = head
p = res
while p.next != None and p.next.next != None:
if p.next.val == p.next.next.val:
temp = p.next.val
while p.next != None and p.next.val == temp:
p.next = p.next.next
else:
p = p.next
return res.next
时间复杂度:O(n),其中 n 为链表结点数,只有一次遍历。
空间复杂度:O(1),只开辟了临时指针,没有额外空间。
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
if head == None:
return None
p = head
a = dict()
while p != None:
if p.val in a:
a[p.val] += 1
else:
a[p.val] = 1
p = p.next
res = ListNode(-1)
res.next = head
p = res
while p.next != None:
if a[p.next.val] != 1:
p.next = p.next.next
else:
p = p.next
return res.next
时间复杂度:O(n),其中 n 为链表结点数,一共两次遍历,每次计数、每次查询都是 O(1)
空间复杂度:O(n),最坏情况下 n 个结点都不相同,哈希表长度为 n
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。