排序算法
快速排序堆排序冒泡排序插入排序简单排序算法归并排序将单链表按照奇偶位置拆分成两个链表[905. 按奇偶排序数组](https://leetcode-cn.com/problems/sort-array-by-parity/)删除链表中重复的节点链表中环的入口结点圆圈中最后剩下的结点两个链表的第一个公共结点复杂链表的复制链表中倒数第K个结点从尾到头打印链表两两交换链表中得结点K个一组翻转链表
排序算法TODO 补充学习排序算法基础
快速排序import javax.naming.PartialResultException;
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] a=new int[]{4,4,6,5,3,2,8,1};
quickSort(a,0, a.length-1);
System.out.println(Arrays.toString(a));
}
private static void quickSort(int[] arr,int startIndex,int endIndex)
{
if(startIndex>=endIndex)
return;
int baseIndex=Partition(arr,startIndex,endIndex);
quickSort(arr,startIndex,baseIndex-1);
quickSort(arr,baseIndex+1,endIndex);
}
private static int Partition(int[] arr,int startIndex,int endIndex)
{
int base=arr[startIndex];
int left=startIndex;
int right=endIndex;
while(leftbase)
right--;
while (left
堆排序
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] arr=new int[]{1,3,2,6,5,7,8,9,10,0};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void heapSort(int[] array)
{
//把无序数组构建成最大堆
for(int i=(array.length-2)/2;i>=0;i--)
{
downAdjust(array,i,array.length);
}
System.out.println(Arrays.toString(array));
for(int i=array.length-1;i>0;i--)
{
int temp=array[i];
array[i]=array[0];
array[0]=temp;
downAdjust(array,0,i);
}
}
private static void downAdjust(int[] array,int parentIndex,int length)
{
//保存父节点值，用于最后赋值
int temp=array[parentIndex];
int childIndex=2*parentIndex+1;
while (childIndexarray[childIndex])
{
childIndex++;
}
//如果父节点大于任何一个孩子的值
if(temp>array[childIndex])
break;
//无须真正交换，单向赋值即可
array[parentIndex]=array[childIndex];
parentIndex=childIndex;
childIndex=2*childIndex+1;
}
array[parentIndex]=temp;
}
}
冒泡排序
import java.util.Arrays;
public class bubbleSort {
public static void main(String[] args) {
int[] arr=new int[]{1,3,2,6,5,7,8,9,10,0};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
private static void bubbleSort(int[] arr)
{
int length=arr.length;
for(int i=0;iarr[j+1])
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
}
}
插入排序
private static void insertSort(int[] arr)
{
int length=arr.length;
int insertNum;
for(int i=1;i=0&&arr[j]>insertNum)
{
arr[j+1]=arr[j];
j--;
}
arr[j+1]=insertNum;
}
}
简单排序算法
private static void selectSort(int[] a)
{
int length=a.length;
for(int i=0;ia[j])
{
min=a[j];
position=j;
}
}
a[position]=a[i];
a[i]=min;
}
}
归并排序
private static void mergeSort(int[] arr,int start,int end)
{
if(start
将单链表按照奇偶位置拆分成两个链表
905. 按奇偶排序数组
给定一个非负整数数组 A，返回一个数组，在该数组中， A 的所有偶数元素之后跟着所有奇数元素。
你可以返回满足此条件的任何数组作为答案。
删除链表中重复的节点
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
ListNode newHead = new ListNode(0); //解决删除头节点的可能
newHead.next=pHead;
ListNode preNode=newHead;
ListNode curNode=pHead;
while (curNode!=null){
if(curNode.next!=null&&curNode.val==curNode.next.val){
while (curNode.next!=null&&curNode.val==curNode.next.val){
curNode=curNode.next;
}
preNode.next=curNode.next;
}
else
{
preNode=curNode;
}
curNode=curNode.next;
}
return newHead.next;
}
}
链表中环的入口结点
public class Solution {
public ListNode EntryNodeOfLoop(ListNode head)
{
if(head==null){
return null;
}
ListNode fastNode=head;
ListNode slowNode=head;
while (fastNode!=null&&fastNode.next!=null){
fastNode=fastNode.next.next;
slowNode=slowNode.next;
if(fastNode==slowNode){
fastNode=head;
while (slowNode!=fastNode){
slowNode=slowNode.next;
fastNode=fastNode.next;
}
return slowNode;
}
}
return null;
}
}
圆圈中最后剩下的结点
//采用数组模拟环的方式
import java.util.ArrayList;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n==0 || m==0){
return -1;
}
//这里为了方便直接使用Java中的容器类了
ArrayList list = new ArrayList<>();
//将所有孩子的编号添加到数组中
for(int i=0;i1){
index = (index+m)%list.size();
list.remove(index);
//由于编号是从0开始的
index--;
}
return list.get(0);
}
}
两个链表的第一个公共结点
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode list1=pHead1;
ListNode list2=pHead2;
while(list1!=list2)
{
list1=(list1==null)?pHead2:list1.next;
list2=(list2==null)?pHead1:list2.next;
}
return list1;
}
}
复杂链表的复制
public class Solution {
public RandomListNode Clone(RandomListNode head)
{
if(pHead==null) return null;
RandomListNode node=pHead;
while(node!=null){
RandomListNode copy = new RandomListNode(node.label);
copy.next=node.next;
node.next=copy;
node=copy.next;
}
node=pHead;
while(node!=null){
if(node.random!=null){
node.next.random=node.random.next;
}
node=node.next.next;
}
node=pHead;
RandomListNode root=pHead.next;
RandomListNode tmp=root;
while(node!=null){
node.next=tmp.next;
tmp.next=node.next==null?null:node.next.next;
node=node.next;
tmp=tmp.next;
}
return root;
}
}
链表中倒数第K个结点
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k<=0){
return null;
}
ListNode fastNode=head;
ListNode slowNode=head;
for(int i=0;i
从尾到头打印链表
import java.util.ArrayList;
public class Solution {
ArrayList arrayList=new ArrayList<>();
public ArrayList printListFromTailToHead(ListNode node){
if(node==null)
return arrayList;
printListFromTailToHead(node.next);
arrayList.add(node.val);
return arrayList;
}
}
两两交换链表中得结点
class Solution {
public ListNode swapPairs(ListNode head) {
// Dummy node acts as the prevNode for the head node
// of the list and hence stores pointer to the head node.
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prevNode = dummy;
while ((head != null) && (head.next != null)) {
// Nodes to be swapped
ListNode firstNode = head;
ListNode secondNode = head.next;
// Swapping
prevNode.next = secondNode;
firstNode.next = secondNode.next;
secondNode.next = firstNode;
// Reinitializing the head and prevNode for next swap
prevNode = firstNode;
head = firstNode.next; // jump
}
// Return the new head node.
return dummy.next;
}
}
K个一组翻转链表
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy=new ListNode(0);
dummy.next=head;
ListNode pre=dummy;
ListNode end=dummy;
while(end.next!=null){
for(int i=0;i 
