反转单向链表
https://leetcode-cn.com/problems/reverse-linked-list/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode next = null; // 下一个节点
while (cur != null) {
// 拿到原来链表head的下一个节点
next = cur.next;
// 把当前链表的下一个节点指向上一个节点也就是pre
cur.next = pre;
// 重置pre为当前链表节点
pre = cur;
// 重置当前节点
cur = next;
}
// 返回反转后的链表 也就是pre 其实就是cur
return pre;
}
}
两两交换链表节点
https://leetcode-cn.com/problems/swap-nodes-in-pairs/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode swapPairs(ListNode head) {
// 初始化一个新的链表
ListNode node = new ListNode(0);
// 设置链表为传入链表
node.next = head;
// 初始化一个临时变量当前链表
ListNode cur = node;
// 循环当前链表 条件是两两不为空
while (cur.next != null && cur.next.next != null) {
// 取出相邻成对节点
ListNode firstNode = cur.next;
ListNode lastNode = firstNode.next;
// 交换节点
// 注意第一次是前面的变成后面，所以还要继续链接后面，所以交换节点的next
firstNode.next = lastNode.next;
// 而第二次直接指向即可
lastNode.next = firstNode;
// 交换完毕 设置当前节点的指向为lastNode
cur.next = lastNode;
// 设置当前节点为往后两个，也就是跳过一对
cur = cur.next.next;
}
return node.next;
}
}
判断链表是否有环
image.png
https://leetcode-cn.com/problems/linked-list-cycle/
-
常见解法
image.png
/**
* 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 slow = head;
ListNode quick = head;
// 对慢指针进行while循环
while (slow.next != null) {
// 如果快指针接下来的节点和接下来两个的节点都为空 则链表结束 不存在闭环
if (quick.next == null || quick.next.next == null) {
return false;
}
// 如果两指针相同 则存在闭环
if (quick.next.next == slow.next) {
return true;
}
// 重置快慢节点 以便于下一次循环
slow = slow.next;
quick = quick.next.next;
}
return false;
}
}
判断字符串的括号是否合法
image.png
https://leetcode-cn.com/problems/valid-parentheses/description/
-
通过压栈的方法来做
image.png
class Solution {
public boolean isValid(String s) {
// 初始化一个栈
Stack<Character> stack = new Stack();
// 把字符串分成字符数组
char[] chars = s.toCharArray();
// 遍历字符数组
for (char aChar : chars) {
// 三种情况 如果栈的大小为0 则把cha插入栈底
if (stack.size() == 0) {
stack.push(aChar);
}else if (isSym(stack.peek(), aChar)) {
// 第二种情况 栈的大小不为0 但是栈底的字符和当前遍历到的字符相等 则移除该对字符
stack.pop();
}else {
stack.push(aChar);
}
}
// 如果stack == 0 则表示栈内的字符成对被移除完毕 则表示字符串的括号是没有问题的 一一对应的
return stack.size() == 0;
}
// 判断括号是否相等
private boolean isSym(char c1, char c2) {
return (c1 == '(' && c2 == ')') || (c1 == '[' && c2 == ']') || (c1 == '{' && c2 == '}');
}
}
用栈实现队列
https://leetcode-cn.com/problems/implement-queue-using-stacks/description/
image.png
从上图可以看出，想要用栈实现队列，其实就是把栈的FILO特性改为队列的FIFO特性。
我们用两个栈倒腾一下顺序就可以实现了。
class MyQueue {
// 声明两个栈
Stack<Integer> stack1, stack2;
/** Initialize your data structure here. */
public MyQueue() {
// 初始化
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
// 往栈1中添加元素
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
// pop使用的是栈2 所以先判断栈2中有木有元素，如果木有，则把栈1中的元素一个个push到栈2中
if (!stack2.isEmpty()) {
return stack2.pop();
}else {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
// 将stack1全部倒腾到stack2之后，拿出stack2的第一个即可
return stack2.pop();
}
/** Get the front element. */
public int peek() {
// 取出栈顶元素 类似于pop
if (!stack2.isEmpty()) {
return stack2.peek();
}else {
while(!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
return stack2.peek();
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/
用队列实现栈
https://leetcode-cn.com/problems/implement-stack-using-queues/
class MyStack {
// 初始化一个队列 先入先出
private Queue<Integer> data;
/** Initialize your data structure here. */
public MyStack() {
data = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
// 添加到末尾
data.offer(x);
// 整体逆序
for (int i = 0; i < data.size() - 1; i++) {
data.offer(data.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return data.poll();
}
/** Get the top element. */
public int top() {
return data.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return data.isEmpty();
}
}
/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/
网友评论