牛客题霸算法刷题记录
链表
删除链表中的重复元素
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @return ListNode类
*/
public ListNode deleteDuplicates (ListNode head) {
// write code here
if(head == null || head.next == null) return head;
ListNode fast = head.next;
ListNode slow = head;
while(fast != null) {
if(fast.val == slow.val) {
fast = fast.next;
slow.next =fast;
} else {
fast = fast.next;
slow = slow.next;
}
}
return head;
}
}
删除链表的倒数第n个节点
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param n int整型
* @return ListNode类
*/
public ListNode removeNthFromEnd (ListNode head, int n) {
// write code here
ListNode pre = head;
ListNode next = head;
for(int i = 0; i < n; i ++) {
next = next.next;
}
if(next == null) return head.next;
//保证pre.next不能等于null
// next.next
while(next != null && next.next != null) {
pre = pre.next;
next = next.next;
}
pre.next = pre.next.next;
return head;
}
}
链表中每k个数进行反转
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode reverseKGroup (ListNode head, int k) {
// write code here
if(head == null || head.next == null || k < 2) return head;
int len = 0;
ListNode cur = head, res = new ListNode(0);
res.next = head;
while(head != null) {
head = head.next;
len ++;
}
ListNode pre = res, next = null;
for(int i = 0; i < len / k; i ++) {
for(int j = 1; j < k; j ++) {
next = cur.next;
if(next != null) {
cur.next = next.next;
} else {
break;
}
next.next = pre.next;
pre.next = next;
}
pre = cur;
cur = cur.next;
}
return res.next;
}
}
合并有序链表
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here
// 不使用额外的节点
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode head = new ListNode(-1);
ListNode res = head;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
head.next = l1;
head = head.next;
l1 = l1.next;
} else {
head.next = l2;
head = head.next;
l2 = l2.next;
}
}
while(l1 != null) {
head.next = l1;
head = head.next;
l1 = l1.next;
}
while(l2 != null) {
head.next = l2;
head = head.next;
l2 = l2.next;
}
return res.next;
}
}
判断一个链表是否有环
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
ListNode pre = head, next = head.next;
while(pre != null && next != null && next.next != null) {
if(pre == next) return true;
pre = pre.next;
next = next.next.next;
}
return false;
}
}
头插法反转链表
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
// 头插法
// 1 2 3 4
ListNode pre = head, next = null;
while(head != null) {
// 保留后面节点信息
next = head.next;
// 断开反转的节点
if(next == null) return pre;
head.next = next.next;
// 利用头插法
next.next = pre;
pre = next;
}
return pre;
}
}
排序
快排
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
// write code here
// Arrays.sort(arr);
quickSort(arr, 0, arr.length-1);
return arr;
}
public void quickSort(int[] q, int l, int r) {
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r >> 1];
int tmp;
while(i < j) {
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j) {
tmp = q[i];
q[i] = q[j];
q[j] = tmp;
}
}
quickSort(q, l, j);
quickSort(q, j + 1, r);
}
}
归并排序
public void mergeSort(int q[], int l, int r) {
if(l >= r) return;
int mid = l + r >> 1;
mergeSort(q, l, mid);
mergeSort(q, mid+1, r);
int k = 0, i = l, j = mid + 1;
while(i <= mid && j <= r) {
if(q[i] <= q[j]) tmp[k ++] = q[i ++];
else tmp[k ++] = q[j ++];
}
while(i <= mid) tmp[k ++] = q[i ++];
while(j <= r) tmp[k ++] = q[j ++];
for(i = l, j = 0; i <= r; i ++, j ++)
q[i] = tmp[j];
}