21xrx.com
2025-03-25 07:07:55 Tuesday
文章检索 我的文章 写文章
Java常见算法题及解析
2023-06-16 16:34:01 深夜i     17     0
Java 算法 二分查找 快速排序 链表反转

Java是一个非常流行的编程语言，许多软件工程师都需要掌握Java中的常见算法。在这篇文章中，我们将介绍一些常见的Java算法题，并给出解析。

1. 二分查找

二分查找是一种常见的查找算法，它的时间复杂度为O(log n)。在Java中，可以使用以下代码实现二分查找：

public static int binarySearch(int[] arr, int key) {
  int low = 0;
  int high = arr.length - 1;
  while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] < key) {
      low = mid + 1;
    } else if (arr[mid] > key)
      high = mid - 1;
     else
      return mid;
    
  }
  return -1;
}

2. 快速排序

快速排序是一种高效的排序算法，它的时间复杂度为O(n log n)。在Java中，可以使用以下代码实现快速排序：

public static void quickSort(int[] arr, int left, int right) {
  if (left < right) {
    int i = left, j = right, pivot = arr[left];
    while (i < j) {
      while (i < j && arr[j] >= pivot)
        j--;
      
      if (i < j) {
        arr[i++] = arr[j];
      }
      while (i < j && arr[i] < pivot) {
        i++;
      }
      if (i < j) {
        arr[j--] = arr[i];
      }
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
  }
}

3. 链表反转

链表反转是一种常见的数据结构问题，它可以使用迭代或递归的方式实现。在Java中，可以使用以下代码实现链表反转：

public static ListNode reverseList(ListNode head) {
  ListNode prev = null;
  ListNode curr = head;
  while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}
  
  

评论区