链表构建and排序

数组（顺序存储）

可以理解为一块连续的内存空间，有了内存空间的首地址，能直接通过索引计算任意位置的元素地址

链表（链式存储）

链表不需要连续的内存空间存储元素，链表元素可以分散在内存空间的不同位置，通过每个节点的next指针，将零散的内存块串联成一个链式的结构。
优点是可以提高内存效率，缺点空间开销比较大

单链表

* 给定一组整数，构造一个单向链表，并实现链表的遍历输出功能；

• 思路：

  先构造 Node 节点类，定义节点的值 val 和指向下一个节点的引用 next。
  insert_node函数实现将一个新的节点插入到链表中的方法。如果链表为空,则直接返回新节点。否则,遍历链表找到最后一个节点,并将新节点添加到链表的末尾。
  create_linked_list函数实现根据给定的数组 arr 创建一个单向链表
  print_linked_list函数实现打印给定链表中的所有节点值

  # 定义节点类
  class Node:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  # 插入新节点
  def insert_node(node, head):
      if head is None: # 首先判断链表是否为空,如果为空,直接返回新节点作为头结点。
          return node 
      else: # 如果链表不为空,则遍历链表
          prev, curr = None, head # 初始化两个指针 prev 和 curr，分别指向链表中的前一个节点和当前节点
          while curr is not None: # 循环遍历整个链表,直到 curr 指针指向 None
              prev = curr # 用 prev 指针记录当前节点的位置,为后续插入新节点做准备
              curr = curr.next # curr 指针移动到下一个节点,继续遍历链表直到找到了链表的最后一个节点(curr 指向 None)。
          prev.next = node # 将 prev 节点的 next 指针指向新节点，实现将新节点插入到链表末尾
          return head
  
  # 创建链表函数
  def create_linked_list(arr):
      # 初始化头结点为None
      head = None
      # 遍历数组,为每个元素创建节点并插入到链表中
      for val in arr:
          node = Node(val)
          head = insert_node(node, head)
      return head
  
  # 打印链表函数
  def print_linked_list(head):
      # 从头结点开始遍历链表,打印每个节点的值
      curr = head
      while curr:
          print(curr.val, end=" ")
          curr = curr.next
  
  # 测试用例
  arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  head = create_linked_list(arr)
  print_linked_list(head)

• 输入数组直接转换单链表

  class ListNode:
      def __init__(self, val):
          self.val = val
          self.next = None
  
  def createLinkedList(arr):
      if not arr:
          return None
      head = ListNode(arr[0])
      curr = head
      for i in range(1, len(arr)):
          curr.next = ListNode(arr[i])
          curr = curr.next
      return head
  
  def printLinkedList(head):
      curr = head
      while curr:
          print(curr.val, end=" ")
          curr = curr.next
      print()
  
  # 测试用例
  arr = [5, 2, 8, 1, 9, 3, 7, 4, 6, 10]
  head = createLinkedList(arr)
  printLinkedList(head)

  * 对输入链表排序，遍历输出排序后的链表；访问链表后面的节点只能依靠 next 指针从头部顺序遍历

  1.冒泡排序 时间复杂度为 O(n^2),空间复杂度为 O(1)

  def bubble_sort_linked_list(head):
      if not head or not head.next:
          return head
      
      dummy = Node(0, head)
      node_i = dummy.next
      tail = None
      
      # 外层循环次数为 链表节点个数
      while node_i:
          node_j = dummy.next
          while node_j and node_j.next != tail:
              if node_j.val > node_j.next.val:
                  # 交换两个节点的值
                  node_j.val, node_j.next.val = node_j.next.val, node_j.val
              node_j = node_j.next
          # 尾指针向前移动 1 位，此时尾指针右侧为排好序的链表
          tail = node_j
          node_i = node_i.next
      
      return dummy.next

  实现：

1. 使用三个指针 node_i、node_j 和 tail。其中 node_i 用于控制外循环次数，循环次数为链节点个数（链表长度）。node_j 和 tail 用于控制内循环次数和循环结束位置。
2. 排序开始前，将 node_i 、node_j 置于头节点位置。tail 指向链表末尾，即 None。
3. 比较链表中相邻两个元素 node_j.val 与 node_j.next.val 的值大小，如果 node_j.val > node_j.next.val，则值相互交换。否则不发生交换。然后向右移动 node_j 指针，直到 node_j.next == tail 时停止。
4. 一次循环之后，将 tail 移动到 node_j 所在位置。相当于 tail 向左移动了一位。此时 tail 节点右侧为链表中最大的链节点。
5. 然后移动 node_i 节点，并将 node_j 置于头节点位置。然后重复第 3、4 步操作。
6. 直到 node_i 节点移动到链表末尾停止，排序结束。
7. 返回链表的头节点 head。

   2.归并排序 时间复杂度为 O(n log n),空间复杂度为 O(log n)

   # 归并排序链表函数
   def sort_linked_list(head):
       # 如果链表为空或只有一个节点,直接返回
       if not head or not head.next:
           return head
   
       # 找到链表中点,将链表拆分为两个链表
       slow, fast = head, head.next
       while fast and fast.next:
           slow = slow.next
           fast = fast.next.next
       mid = slow.next
       slow.next = None
   
       # 递归排序两个子链表
       left = sort_linked_list(head)
       right = sort_linked_list(mid)
   
       # 合并两个已排序的子链表
       return merge_lists(left, right)
   
   def merge_lists(left, right):
       dummy = Node()
       curr = dummy
       while left and right:
           if left.val < right.val:
               curr.next = left
               left = left.next
           else:
               curr.next = right
               right = right.next
           curr = curr.next
       if left:
           curr.next = left
       if right:
           curr.next = right
       return dummy.next
   # 测试用例
   arr = [5, 2, 8, 1, 9, 3, 7, 4, 6, 10]
   head = create_linked_list(arr)
   print("Original list:")
   print_linked_list(head)
   print("\nSorted list:")
   bubble_sorted_head = bubble_sort_linked_list(head)
   print_linked_list(bubble_sorted_head)
   print("\n")
   sorted_head = sort_linked_list(head)
   print_linked_list(sorted_head)

   实现：

• sort_linked_list(head) 函数:首先判断链表是否为空或只有一个节点,如果是,直接返回。
• 否则,使用快慢指针找到链表的中点,将链表拆分为两个子链表。递归地对两个子链表进行排序。
• 最后调用 merge_lists() 函数合并两个有序的子链表。
• merge_lists(left, right) 函数:创建一个哑结点 dummy,用于存储最终合并后的链表。比较 left 和 right 链表的当前节点值,将较小的节点接到合并链表的末尾。当其中一个链表为空时,将剩余的节点直接接到合并链表的末尾。最后返回合并后链表的头结点 dummy.next。