1 单链表与双链表的简单练习
题目1：单链表和双链表如何反转
01 单链表反转
//反转链表public static ListNode reverseListNode(ListNode head) {if (head == null || head.next == null) {return head;}ListNode pre = null;ListNode next = null;while (head != null) {next = head.next;head.next = pre;pre = head;head = next;}return pre;}/*以下代码为对数器，测试单链表反转*///对数器，用List容器实现链表反转public static ListNode comarator(ListNode head) {if (head == null || head.next == null) {return head;}List<ListNode> list = new ArrayList<>();while (head != null) {list.add(head);head = head.next;}list.get(0).next = null;for (int i = 1; i < list.size(); i++) {list.get(i).next = list.get(i - 1);}return list.get(list.size() - 1);}//生成随机链表public static ListNode generateRandomListNode(int listLength, int maxValue) {ListNode cur = new ListNode(((int) (Math.random() * maxValue) - (int) (Math.random() * maxValue)), null);//保证生成的链表至少有1个节点ListNode head = cur;int length = (int) (Math.random() * listLength + 1);for (int i = 0; i < length - 1; i++) {cur.next = new ListNode(((int) (Math.random() * maxValue) - (int) (Math.random() * maxValue)), null);cur = cur.next;}return head;}检查两个链表结构是否一致public static boolean check(ListNode head1, ListNode head2) {if (head1 == null && head2 == null) {return true;}if (head1 != null ^ head2 != null) {return false;}while (head1 != null && head2 != null) {if (head1.data != head2.data) {return false;}head1 = head1.next;head2 = head2.next;if (head1 != null ^ head2 != null) {return false;}}return true;}//打印单链表public static void printListNode(ListNode head) {if (head == null) {return;}while (head != null) {System.out.print(head.data + " ");head = head.next;}System.out.println();}//复制一个单链表结构public static ListNode copyListNode(ListNode head) {if (head == null) {return head;}ListNode ans = new ListNode(head.data, null);ListNode cur = ans;while (head.next != null) {cur.next = new ListNode(head.next.data, null);cur = cur.next;head = head.next;}return ans;}
02 双链表反转
/*双链表反转*/public static DoubleListNode reverseDoubleListNode(DoubleListNode head) {if (head == null || head.next == null) {return head;}DoubleListNode pre = null;DoubleListNode next = null;while (head != null) {next = head.next;head.next = pre;head.prev = next;pre = head;head = next;}return pre;}/*以下代码为对数器，用于测试*/public static DoubleListNode comparator(DoubleListNode head) {if (head == null || (head.next == null && head.prev == null)) {return head;}List<DoubleListNode> list = new ArrayList<>();while (head != null) {list.add(head);head = head.next;}list.get(0).next = null;list.get(0).prev = list.get(1);for (int i = 1; i < list.size(); i++) {list.get(i).next = list.get(i - 1);if (i == list.size() - 1) {list.get(i).prev = null;} else {list.get(i).prev = list.get(i + 1);}}return list.get(list.size() - 1);}public static DoubleListNode generateRandomDoubleListNode(int maxLength, int maxValue) {//保证至少有一个节点int length = (int) (Math.random() * maxLength + 1);DoubleListNode head = new DoubleListNode((int) (Math.random() * maxValue + 1) - (int) (Math.random() * maxValue + 1), null, null);DoubleListNode cur = head;for (int i = 0; i < length - 1; i++) {DoubleListNode next = new DoubleListNode((int) (Math.random() * maxValue + 1) - (int) (Math.random() * maxValue + 1), null, null);cur.next = next;next.prev = cur;cur = next;}return head;}public static DoubleListNode copyDoubleListNode(DoubleListNode head) {if (head == null) {return null;}DoubleListNode ans = new DoubleListNode(head.data, null, null);DoubleListNode cur = ans;while (head.next != null) {DoubleListNode next = new DoubleListNode(head.next.data, null, null);cur.next = next;next.prev = cur;cur = next;head = head.next;}return ans;}public static boolean check(DoubleListNode head1, DoubleListNode head2) {if (head1 == null && head2 == null) {return true;}if (head1 != null ^ head2 != null) {return false;}DoubleListNode end1 = null;DoubleListNode end2 = null;//正向比较while (head1 != null && head2 != null) {if (head1.data != head1.data) {return false;}end1 = head1;end2 = head2;head1 = head1.next;head2 = head2.next;if (head1 != null ^ head2 != null) {return false;}}//逆向比较while (end1 != null && end2 != null) {if (end1.data != end1.data) {return false;}end1 = end1.prev;end2 = end2.prev;if (end1 != null ^ end2 != null) {return false;}}return true;}public static void printDoubleListNode(DoubleListNode head) {if (head == null) {return;}DoubleListNode end = null;while (head != null) {System.out.print(head.data+" ");end = head;head = head.next;}System.out.println();while (end != null) {System.out.print(end.data+" ");end = end.prev;}System.out.println();}
题目2：把给定值都删除
/*把给定值都删除
*/
public static ListNode deleteGivenValue(ListNode head, int value) {
while (head != null && head.data == value) {
head = head.next;
}
if (head == null) {
return null;
}
ListNode cur = head;
ListNode next = cur.next;
while (next != null) {
cur.next = null;
if (next.data != value) {
cur.next = next;
cur = next;
}
next = next.next;
}
return head;
}
/*以下为对数器，用于测试*/
public static ListNode comparator(ListNode head, int value) {
if (head == null) {
return null;
}
LinkedList<Integer> list = new LinkedList<>();
while (head != null) {
list.add(Integer.valueOf(head.data));
head = head.next;
}
int count = 0;
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == value) {
count++;
}
}
for (int i = 0; i < count; i++) {
list.remove(Integer.valueOf(value));
}
if (list.size() == 0) {
return null;
}
head = new ListNode(list.get(0));
ListNode cur = head;
for (int i = 1; i < list.size(); i++) {
ListNode next = new ListNode(list.get(i));
cur.next = next;
cur = next;
}
return head;
}
public static ListNode generateRandomListNode(int maxLength, int maxValue, int value) {
int length = (int) (Math.random() * (maxLength + 1));
if (length == 0) {
return null;
}
ListNode head = new ListNode((int) (Math.random() * maxValue + 1) - (int) (Math.random() * maxValue + 1));
ListNode cur = head;
for (int i = 0; i < length - 1; i++) {
double random = Math.random();
ListNode next = null;
if (random < 0.5) {
next = new ListNode((int) (Math.random() * maxValue + 1));
} else {
next = new ListNode(value);
}
cur.next = next;
cur = next;
}
return head;
}
public static boolean check(ListNode head1, ListNode head2) {
if (head1 == null && head2 == null) {
return true;
}
if (head1 != null ^ head2 != null) {
return false;
}
while (head1 != null && head2 != null) {
if (head1.data != head2.data) {
return false;
}
head1 = head1.next;
head2 = head2.next;
if (head1 != null ^ head2 != null) {
return false;
}
}
return true;
}
public static ListNode copyListNode(ListNode head) {
if (head == null) {
return head;
}
ListNode ans = new ListNode(head.data);
ListNode cur = ans;
while (head.next != null) {
cur.next = new ListNode(head.next.data);
cur = cur.next;
head = head.next;
}
return ans;
}
public static void printListNode(ListNode head) {
if (head == null) {
return;
}
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
2 栈和队列
题目1：双链表实现栈和队列
01 双链表实现栈
static class DoubleListNode<T> {
public T data;
public DoubleListNode<T> prev;
public DoubleListNode<T> next;
public DoubleListNode(T data) {
this.data = data;
}
}
static class MyStack<T> {
private DoubleListNode<T> head;
public MyStack() {
}
//push
public void push(T num) {
if (head == null) {
head = new DoubleListNode<>(num);
} else {
DoubleListNode next = new DoubleListNode<>(num);
head.next = next;
next.prev = head;
head = next;
}
}
//pop
public T pop() {
if (head == null) {
return null;
}
T data = head.data;
head = head.prev;
return data;
}
//isEmpty
public boolean isEmpty() {
return head == null;
}
}
02 双链表实现队列
static class MyDeque<T> {
DoubleListNode<T> head;
DoubleListNode<T> end;
public MyDeque() {
}
public void addFirst(T num) {
DoubleListNode<T> cur = new DoubleListNode(num);
if (head == null) {
head = cur;
end = cur;
} else {
cur.next = head;
head.prev = cur;
head = cur;
}
}
public void addLast(T num) {
DoubleListNode<T> cur = new DoubleListNode(num);
if (head == null) {
head = cur;
end = head;
} else {
cur.prev = end;
end.next = cur;
end = cur;
}
}
public T popFirst() {
if (head == null) {
return null;
}
T data = head.data;
if (head == end) {
head = null;
end = null;
} else {
head = head.next;
head.prev = null;
}
return data;
}
public T popLast() {
if (end == null) {
return null;
}
T data = end.data;
if (end == head) {
end = null;
head = null;
} else {
end = end.prev;
end.next = null;
}
return data;
}
public boolean isEmpty() {
return head == null && end == null;
}
}
题目2：数组实现栈和队列
01 数组实现栈
static class MyStack {
private int[] arr;
private static final int DEAUFAL_LENGTH = 16;
private static int endIndex;
private static int length;
public MyStack() {
}
public void push(int num) {
if (arr == null) {
arr = new int[DEAUFAL_LENGTH];
length = arr.length;
endIndex = 0;
arr[endIndex++] = num;
} else {
if (endIndex == length) {
length = length + (length >> 1);
int[] newArr = new int[length];
System.arraycopy(arr, 0, newArr, 0, arr.length);
arr = newArr;
}
arr[endIndex++] = num;
}
}
public Integer pop() {
if (arr == null && endIndex == 0) {
return null;
}
return arr[--endIndex];
}
public boolean isEmpty() {
return endIndex == 0;
}
}
02 数组实现队列
/**
* 数组实现队列
*/
static class MyQueue {
private final int[] arr;
private final int length;
private int size;
private int pushIndex;
private int popIndex;
private MyQueue(int length) {
this.length = length;
arr = new int[length];
pushIndex = 0;
popIndex = 0;
}
public static MyQueue getQueue(int length) {
return new MyQueue(length);
}
public void push(int num) throws RuntimeException {
if (size == length) {
throw new RuntimeException("队列已满，添加失败");
}
arr[pushIndex] = num;
size++;
pushIndex = nextIndex(pushIndex);
}
public Integer pop() throws RuntimeException {
if (size == 0) {
return null;
}
int ans = arr[popIndex];
popIndex = nextIndex(popIndex);
size--;
return ans;
}
public boolean isEmpty() {
return size == 0;
}
private int nextIndex(int index) {
return index < length - 1 ? index + 1 : 0;
}
}
题目3：实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
/*
* 实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能
1）pop、push、getMin操作的时间复杂度都是 O(1)。
2）设计的栈类型可以使用现成的栈结构。
*/
static class MyStack {
private Stack<Integer> stack;
private Stack<Integer> minValueStack;
private int minValue;
public MyStack() {
stack = new Stack<>();
minValueStack = new Stack<>();
}
public void push(int num) {
if (minValueStack.isEmpty()) {
minValue = num;
} else {
minValue = minValueStack.peek() < num ? minValueStack.peek() : num;
}
stack.push(num);
minValueStack.push(minValue);
}
public Integer pop() {
if (stack.isEmpty()) {
return null;
}
minValueStack.pop();
return stack.pop();
}
public Integer getMin() {
if (minValueStack.isEmpty()) {
return null;
}
return minValueStack.peek();
}
public boolean isEmpty(){
return stack.isEmpty();
}
}
题目4：用栈结构实现队列
//如何用栈结构实现队列结构
static class MyQueue {
private Stack<Integer> pushStack;
private Stack<Integer> popStack;
public MyQueue() {
pushStack = new Stack<>();
popStack = new Stack<>();
}
public void add(int num) {
pushStack.push(num);
}
public Integer poll() {
if (popStack.empty() && pushStack.empty()) {
return null;
}
pushStackPollToPopStack();
return popStack.pop();
}
public Integer peek() {
if (popStack.empty() && pushStack.empty()) {
return null;
}
pushStackPollToPopStack();
return popStack.peek();
}
public boolean isEmpty() {
return pushStack.isEmpty() && popStack.isEmpty();
}
private void pushStackPollToPopStack() {
if (popStack.empty()) {
while (!pushStack.empty()) {
popStack.push(pushStack.pop());
}
}
}
}
题目5：用队列结构实现栈
static class MyStack {
private Queue<Integer> pushQueue;
private Queue<Integer> popQueue;
public MyStack() {
pushQueue = new LinkedList<>();
popQueue = new LinkedList<>();
}
public void push(int num) {
pushQueue.add(num);
}
public Integer pop() {
while (pushQueue.size() > 1) {
popQueue.add(pushQueue.poll());
}
Integer ans = pushQueue.poll();
Queue<Integer> temp = pushQueue;
pushQueue = popQueue;
popQueue = temp;
return ans;
}
public Integer peek() {
while (pushQueue.size() > 1) {
popQueue.add(pushQueue.poll());
}
Integer ans = pushQueue.poll();
popQueue.add(ans);
Queue<Integer> temp = pushQueue;
pushQueue = popQueue;
popQueue = temp;
return ans;
}
public boolean isEmpty() {
return pushQueue.isEmpty();
}
}
3 递归时间复杂度估算
若有收获，就点个赞吧
0 人点赞
