单链表基础概念
首先，让我们来回顾一下单链表的基本概念。单链表是一种常见的数据结构，由一系列节点组成，每个节点包含两个部分：数据和指向下一个节点的指针。单链表的特点是每个节点只知道下一个节点的位置，而不知道上一个节点的位置。
节点结构
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
单链表操作
- 创建单链表：从尾部开始添加节点，最后一个节点的
next指针为None。 - 插入节点：在链表的指定位置插入一个新节点。
- 删除节点：删除链表中的指定节点。
- 遍历链表：按照顺序访问链表中的每个节点。
- 反转链表：将链表中的节点顺序颠倒。
单链表习题
下面是一些单链表的经典习题，通过解决这些问题，你可以更加熟练地掌握单链表的操作。
习题一：反转链表
题目描述：给定一个单链表的头节点head，请编写一个函数，实现链表的反转。
思路：使用三个指针pre、cur和next，其中pre用于保存当前节点的前一个节点，cur用于遍历链表，next用于保存当前节点的下一个节点。
代码实现：
def reverse_list(head):
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
习题二：删除链表中的重复元素
题目描述：给定一个单链表的头节点head，请编写一个函数，删除链表中重复的元素。
思路：使用两个指针pre和cur，其中pre用于遍历链表，cur用于比较当前节点和下一个节点的值。
代码实现：
def delete_duplicates(head):
pre = head
while pre and pre.next:
if pre.value == pre.next.value:
pre.next = pre.next.next
else:
pre = pre.next
return head
习题三：判断链表是否存在环
题目描述：给定一个单链表的头节点head，请编写一个函数，判断链表是否存在环。
思路：使用两个指针slow和fast，其中slow每次移动一个节点，fast每次移动两个节点。如果链表中存在环，那么slow和fast最终会相遇。
代码实现：
def has_cycle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
习题四：合并两个有序链表
题目描述：给定两个有序链表l1和l2，请编写一个函数，合并这两个链表为一个新的有序链表。
思路：创建一个新的头节点dummy，然后使用两个指针pre和cur，其中pre用于遍历新链表，cur用于比较两个有序链表中的节点。
代码实现：
def merge_two_lists(l1, l2):
dummy = ListNode(0)
pre = dummy
while l1 and l2:
if l1.value < l2.value:
pre.next = l1
l1 = l1.next
else:
pre.next = l2
l2 = l2.next
pre = pre.next
pre.next = l1 if l1 else l2
return dummy.next
总结
通过以上习题的练习，相信你已经对单链表有了更深入的了解。在实际开发中，单链表的应用非常广泛，如实现栈、队列等数据结构。希望这些习题能够帮助你更好地掌握单链表，为你的编程之路打下坚实的基础。