环形链表
使用两个指针，一个指针走一步，一个指针走两步，如果存在环，则两个指针必然会相遇，否则不会，用python实现如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
def hasCycle(self, head: Optional[ListNode]) -> bool:
if not head and not head.next:return False
tail1 = head
tail2 = head.next
while tail1 and tail2:
if tail1 == tail2:
return True
tail1 = tail1.next
tail2 = tail2.next
if tail2:
tail2 = tail2.next
else:
return False
return False两数相加
用python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head = None
tail = None
add = 0
while l1!=None and l2!=None:
val = l1.val + l2.val + add
add = int(val / 10)
val = val % 10
if head == None:
head = ListNode(val)
tail = head
else:
temp = ListNode(val)
tail.next = temp
tail = tail.next
l1 = l1.next
l2 = l2.next
# 因为l1和l2的节点数都大于等于1，所以此处head一定不为空
while l1:
val = l1.val + add
add = int(val / 10)
val = val % 10
temp = ListNode(val)
tail.next = temp
tail = tail.next
l1 = l1.next
while l2:
val = l2.val + add
add = int(val / 10)
val = val % 10
temp = ListNode(val)
tail.next = temp
tail = tail.next
l2 = l2.next
#
if add >0:
temp = ListNode(add)
tail.next = temp
return head反转链表 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if left == right:return head
start_node = None
start_pre_node = None
end_node = None
end_next_node = None
p = head
i = 1
pre = None
while p and i<=right:
print(p.val)
if i < left:
pre = p
p = p.next
elif i == left:
start_pre_node = pre
start_node = p
pre = p
p = p.next
elif i == right:
end_node = p
end_next_node = p.next
p.next = pre
else :
temp = p.next
p.next = pre
pre = p
p = temp
i += 1
if start_pre_node:
start_pre_node.next = end_node
else:
head = end_node
start_node.next = end_next_node
return headK 个一组翻转链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if k == 1:return head
p = head
node_size = 0
while p:
p = p.next
node_size += 1
node_size = int(node_size/k) * k
if node_size == 0:return head
start_node = None
start_pre_node = None
pre = None
p = head
i = 1
while i<=node_size:
if i%k == 1:
start_node = p
pre = p
p = p.next
elif i%k >0:
temp = p.next
p.next = pre
pre = p
p = temp
else:
temp = p.next
p.next = pre
pre = p
p = temp
if start_pre_node:
start_pre_node.next = pre
else:
head = pre
start_pre_node = start_node
i += 1
start_pre_node.next = p
return head删除链表的倒数第 N 个结点
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
node_size = 0
p = head
while p:
p=p.next
node_size += 1
remove_index = node_size - n
if remove_index == 0:
return head.next
p = head
i = 0
pre = None
while i<remove_index:
pre = p
p = p.next
i += 1
pre.next = p.next
return head删除排序链表中的重复元素 II
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
p = head
pre = None
while p:
if (p.next == None) or (p.next and p.next.val != p.val):
if not pre:
head = p
else:
pre.next = p
pre = p
p = p.next
else:
val = p.val
while p and p.val == val:
p = p.next
if pre:
pre.next = p
return head
else:
return None旋转链表
# 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:return None
node_size = 1
p = head
while p.next:
p = p.next
node_size += 1
index = k%node_size
if index == 0:return head
p.next = head
p = head
i = 0
pre = None
while i<node_size-index:
pre = p
p = p.next
i += 1
pre.next = None
return p分隔链表
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
if not head:return None
tail1 = None
tail2 = None
head1 = None
head2 = None
p = head
while p:
if p.val < x:
if head1 == None:
head1 = p
tail1 = p
else:
tail1.next = p
tail1 = p
else:
if head2 == None:
head2 = p
tail2 = p
else:
tail2.next = p
tail2 = p
p = p.next
if head1 != None:
if head2 != None:
tail1.next = head2
tail2.next = None
return head1
else:
return head2