# 1. 定义一个链表节点
class ListNode:
def __init__(self, val=0, next_node=None):
self.val = val
self.next_node = next_node
# 2. 定义一个 node头节点
class LinkedList:
def __init__(self):
self.head = None
# 3.链表查找元素 get(index)：
def get_node(self, index):
count = 0
cur = self.head
while cur is not None and count < index - 1:
count += 1
cur = cur.next_node
if cur is None:
return -1
return cur.val
# 4.1 链表头部插入元素
def insert_head(self, val):
node = ListNode(val)
node.next_node = self.head.next_node
self.head.next_node = node
# 4.2 链表尾部插入元素
def insert_tail(self, val):
node = ListNode(val)
cur = self.head
# 遍历链表 直到尾部
while cur.next_node is not None:
cur = cur.next_node
cur.next_node = node
# 4.3 链表中第i个元素后插入元素
def insert_inside(self, index, val):
count = 1
cur = self.head
if index <= 0:
node = ListNode(val)
node.next_node = self.head.next_node
self.head.next_node = node
while cur is not None and count < index - 1:
count += 1
cur = cur.next_node
if cur is None:
return -1
node = ListNode(val)
node.next_node = cur.next_node
cur.next_node = node
# 链表 删除第i个元素
def remove_inside(self, index):
count = 0
cur = self.head
while cur.next_node and count < index - 1:
count += 1
cur = cur.next_node
if cur is None:
return -1
del_node = cur.next_node
cur.next_node = del_node.next_node
# 翻转 链表
class Solution1:
def reverse_list(self, head: ListNode) -> ListNode:
cur, pre = head, None
while cur:
tmp = cur.next # 暂存后继节点 这里存储的是第二个节点
cur.next = pre # 修改 next 引用指向，这里指向的是最后一个元素
pre = cur # pre 当前节点完成修改指向操作后,pre指向当前节点
cur = tmp # cur 当前节点完成修改指向操作后,cur指向下一个节点
return pre
# 删除链表指定元素
class Solution2:
def remove_elements(self, head: ListNode, val: int) -> ListNode:
# 先移除头元素
while head is not None and head.val == val:
head = head.next
if head is None:
return
# 再移除后续元素
pre = head
while pre.next:
if pre.next.val == val:
pre.next = pre.next.next
else:
pre = pre.next
return head
# 奇偶链表
class Solution3:
def oddEvenList(self, head: ListNode) -> ListNode:
if not head:return head
odd = head
even_head = even = head.next
while odd.next and even.next: # 这里面的条件存在 如果当链表是奇数个
# 奇数的下下个是奇数 同理偶数也一样
odd.next = odd.next.next
even.next = even.next.next
# 奇数链表和奇数链表拼接 偶数同理
odd,even = odd.next,even.next
odd.next = even_head
return head
# 回文链表
class Solution4:
def isPalindrome(self, head: ListNode) -> bool:
vals = []
current_node = head
while current_node is not None:
vals.append(current_node.val)
current_node = current_node.next
return vals == vals[::-1]
# 深拷贝随机链表
class Solution5:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
dummy = Node(-1000000)
newCurr = dummy
curr = head
node2node = {}
while curr:
n = Node(curr.val, curr.next, curr.random)
node2node[curr] = n
newCurr.next = n
newCurr = newCurr.next
curr = curr.next
curr = dummy.next
while curr:
if curr.random:
curr.random = node2node[curr.random]
curr = curr.next
return dummy.next
# 链表 插入排序
class Solution6:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
dummy = ListNode(float('-inf'))
node1,node2 = dummy,head
while node2:
nt = node2.next
while node1.next and node1.next.val<=node2.val:
node1 = node1.next
node1.next,node2.next = node2,node1.next
node1,node2 = dummy,nt
return dummy.next
# 合并两个有序链表
class Solution7:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: return l2 # 终止条件，直到两个链表都空
if not l2: return l1
if l1.val <= l2.val: # 递归调用
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next = self.mergeTwoLists(l1,l2.next)
return l2
# 归并排序 排序列表
class Solution8:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return head
dummy = ListNode(float('-inf'))
def merge(left, right):
node = dummy
while left and right:
if left.val < right.val:
node.next = left
node = left
left = left.next
else:
node.next = right
node = right
right = right.next
node.next = left if left else right
return dummy.next
def merge_sort(head):
fast = slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
slow.next,slow = None,slow.next
left = merge_sort(head) if head.next else head
right = merge_sort(slow) if slow.next else slow
return merge(left, right)
return merge_sort(head)
# 环形链表 快慢指针
class Solution9:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head == None or head.next == None: return False
slow = head
fast = head.next
while fast != slow:
if fast.next == None or fast.next.next == None: return False
slow = slow.next
fast = fast.next.next
return True
# 环形链表 2
class Solution10(object):
def detectCycle(self, head):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
# 删除倒数第n个节点
class Solution11:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
pre = ListNode(0, head) # 伪头节点
node = pre # 当前节点，初始化为伪头节点
idx = 0 # 节点编号，初始为0
node_map = {} # 哈希表存储节点编号和节点
while node: # 遍历链表，idx最终为节点总个数
node_map[idx] = node
node = node.next
idx += 1
node_map[idx - n - 1].next = node_map[idx - n].next # 根据节点编号获取删除节点的前一个节点和要删除的节点
return pre.next # 返回头节点
