链表刷题TOP202

**链表刷题 TOP202**

链表是一种常见的数据结构，广泛应用于计算机科学中。链表刷题是程序员们经常遇到的一个问题。下面我们将列出一些常见的链表刷题，以及它们的解法和代码示例。

###1. 链表的基本操作#### 题目描述：

* 创建一个链表* 插入一个新节点到链表中* 删除一个节点从链表中* 打印链表中的所有元素#### 解法：

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def insert(self, data):
 if not self.head:
 self.head = Node(data)
 else:
 current_node = self.head while current_node.next:
 current_node = current_node.next current_node.next = Node(data)

 def delete(self, key):
 if self.head is None:
 return # If the node to be deleted is head node if self.head.data == key:
 self.head = self.head.next return # Search for the node to be deleted and update the links current_node = self.head while current_node.next:
 if current_node.next.data == key:
 break current_node = current_node.next if current_node.next is None and current_node.data != key:
 print("Node not found")
 return # If node to be deleted is head node, then change the head pointer if current_node.next.data == key:
 current_node.next = current_node.next.next def print_list(self):
 temp = self.head while temp:
 print(temp.data, end=" ")
 temp = temp.next print()

# Example usagelinked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

print("Linked List:")
linked_list.print_list() # Output:123linked_list.delete(2)

print("Linked List after deletion:")
linked_list.print_list() # Output:13

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def reverse(self):
 prev_node = None current_node = self.head while current_node:
 next_node = current_node.next # Store the next node temporarily current_node.next = prev_node # Reverse the link of the current node prev_node = current_node # Move prev_node and current_node one step forward current_node = next_node self.head = prev_node # Update head pointer to point to the new first node def print_list(self):
 temp = self.head while temp:
 print(temp.data, end=" ")
 temp = temp.next print()

# Example usagelinked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

print("Original Linked List:")
linked_list.print_list() # Output:123linked_list.reverse()

print("Reversed Linked List:")
linked_list.print_list() # Output:321

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def find_middle(self):
 slow_ptr = self.head fast_ptr = self.head if self.head is not None:
 while fast_ptr is not None and fast_ptr.next is not None:
 fast_ptr = fast_ptr.next.next # Move fast_ptr two steps at a time slow_ptr = slow_ptr.next # Move slow_ptr one step at a time return slow_ptr.data # Return the data of the middle node def print_list(self):
 temp = self.head while temp:
 print(temp.data, end=" ")
 temp = temp.next print()

# Example usagelinked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

print("Middle Node of Linked List:")
print(linked_list.find_middle()) # Output:2

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def length(self):
 count =0 temp = self.head while temp:
 count +=1 temp = temp.next return count def print_list(self):
 temp = self.head while temp:
 print(temp.data, end=" ")
 temp = temp.next print()

# Example usagelinked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

print("Length of Linked List:")
print(linked_list.length()) # Output:3

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def merge(self, other_list):
 if not self.head and not other_list.head:
 return None if not self.head:
 return other_list if not other_list.head:
 return self current_node1 = self.head current_node2 = other_list.head while current_node1.next and current_node2:
 next_node1 = current_node1.next next_node2 = current_node2.next # Merge smaller value first if current_node1.data <= current_node2.data:
 current_node1.next = next_node1 current_node1 = next_node1 else:
 current_node2.next = next_node2 current_node2 = next_node2 # If there are remaining nodes in either list, append them to the end of the merged list if current_node1:
 current_node2.next = current_node1 elif current_node2:
 self.head = current_list def print_list(self):
 temp = self.head while temp:
 print(temp.data, end=" ")
 temp = temp.next print()

# Example usagelinked_list1 = LinkedList()
linked_list1.insert(1)
linked_list1.insert(3)

linked_list2 = LinkedList()
linked_list2.insert(2)
linked_list2.insert(4)

print("Merged Linked List:")
linked_list1.merge(linked_list2).print_list() # Output:1234

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def delete_all(self):
 current_node = self.head while current_node:
 next_node = current_node.next # Store the next node temporarily del current_node # Delete the current node current_node = next_node self.head = None # Update head pointer to point to None def print_list(self):
 temp = self.head while temp:
 print(temp.data, end=" ")
 temp = temp.next print()

# Example usagelinked_list = LinkedList()
linked_list.insert(1)
linked_list.insert(2)
linked_list.insert(3)

print("Original Linked List:")
linked_list.print_list() # Output:123linked_list.delete_all()

print("Linked List after deletion:")
linked_list.print_list() # Output:

class Node:
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def reverse(self):
 prev_node = None current_node = self.head while current_node:
 next_node = current_node.next # Store the next node temporarily current_node.next = prev_node # Reverse the link of the current node prev_node = current_node # Move to the previous node