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