【算法数据结构初阶篇】：链表问题
一、反转单双链表
一、数据结构图
二、代码演示
public class Code01_ReverseList {
public static class Node {
public int value;
public Node next;
public Node(int data) {
value = data;
}
}
public static class DoubleNode {
public int value;
public DoubleNode last;
public DoubleNode next;
public DoubleNode(int data) {
value = data;
}
}
public static Node reverseLinkedList(Node head) {
Node pre = null;
Node next = null;
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
public static DoubleNode reverseDoubleList(DoubleNode head) {
DoubleNode pre = null;
DoubleNode next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}二、单链表实现队列和栈
特点：
队列：先进先出
栈： 先进后出
一、代码演示
package class04;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Code02_LinkedListToQueueAndStack {
public static class Node<V> {
public V value;
public Node<V> next;
public Node(V v) {
value = v;
next = null;
}
}
public static class MyQueue<V> {
private Node<V> head;
private Node<V> tail;
private int size;
public MyQueue() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void offer(V value) {
Node<V> cur = new Node<V>(value);
if (tail == null) {
head = cur;
tail = cur;
} else {
tail.next = cur;
tail = cur;
}
size++;
}
// C/C++的同学需要做节点析构的工作
public V poll() {
V ans = null;
if (head != null) {
ans = head.value;
head = head.next;
size--;
}
if (head == null) {
tail = null;
}
return ans;
}
// C/C++的同学需要做节点析构的工作
public V peek() {
V ans = null;
if (head != null) {
ans = head.value;
}
return ans;
}
}
public static class MyStack<V> {
private Node<V> head;
private int size;
public MyStack() {
head = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void push(V value) {
Node<V> cur = new Node<>(value);
if (head == null) {
head = cur;
} else {
cur.next = head;
head = cur;
}
size++;
}
public V pop() {
V ans = null;
if (head != null) {
ans = head.value;
head = head.next;
size--;
}
return ans;
}
public V peek() {
return head != null ? head.value : null;
}
}
public static void testQueue() {
MyQueue<Integer> myQueue = new MyQueue<>();
Queue<Integer> test = new LinkedList<>();
int testTime = 5000000;
int maxValue = 200000000;
System.out.println("测试开始！");
for (int i = 0; i < testTime; i++) {
if (myQueue.isEmpty() != test.isEmpty()) {
System.out.println("Oops!");
}
if (myQueue.size() != test.size()) {
System.out.println("Oops!");
}
double decide = Math.random();
if (decide < 0.33) {
int num = (int) (Math.random() * maxValue);
myQueue.offer(num);
test.offer(num);
} else if (decide < 0.66) {
if (!myQueue.isEmpty()) {
int num1 = myQueue.poll();
int num2 = test.poll();
if (num1 != num2) {
System.out.println("Oops!");
}
}
} else {
if (!myQueue.isEmpty()) {
int num1 = myQueue.peek();
int num2 = test.peek();
if (num1 != num2) {
System.out.println("Oops!");
}
}
}
}
if (myQueue.size() != test.size()) {
System.out.println("Oops!");
}
while (!myQueue.isEmpty()) {
int num1 = myQueue.poll();
int num2 = test.poll();
if (num1 != num2) {
System.out.println("Oops!");
}
}
System.out.println("测试结束！");
}
public static void testStack() {
MyStack<Integer> myStack = new MyStack<>();
Stack<Integer> test = new Stack<>();
int testTime = 5000000;
int maxValue = 200000000;
System.out.println("测试开始！");
for (int i = 0; i < testTime; i++) {
if (myStack.isEmpty() != test.isEmpty()) {
System.out.println("Oops!");
}
if (myStack.size() != test.size()) {
System.out.println("Oops!");
}
double decide = Math.random();
if (decide < 0.33) {
int num = (int) (Math.random() * maxValue);
myStack.push(num);
test.push(num);
} else if (decide < 0.66) {
if (!myStack.isEmpty()) {
int num1 = myStack.pop();
int num2 = test.pop();
if (num1 != num2) {
System.out.println("Oops!");
}
}
} else {
if (!myStack.isEmpty()) {
int num1 = myStack.peek();
int num2 = test.peek();
if (num1 != num2) {
System.out.println("Oops!");
}
}
}
}
if (myStack.size() != test.size()) {
System.out.println("Oops!");
}
while (!myStack.isEmpty()) {
int num1 = myStack.pop();
int num2 = test.pop();
if (num1 != num2) {
System.out.println("Oops!");
}
}
System.out.println("测试结束！");
}
public static void main(String[] args) {
testQueue();
testStack();
}
}
三、双链表实现双端队列
一、代码演示
package class04;
import java.util.Deque;
import java.util.LinkedList;
public class Code03_DoubleLinkedListToDeque {
public static class Node<V> {
public V value;
public Node<V> last;
public Node<V> next;
public Node(V v) {
value = v;
last = null;
next = null;
}
}
public static class MyDeque<V> {
private Node<V> head;
private Node<V> tail;
private int size;
public MyDeque() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void pushHead(V value) {
Node<V> cur = new Node<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
cur.next = head;
head.last = cur;
head = cur;
}
size++;
}
public void pushTail(V value) {
Node<V> cur = new Node<>(value);
if (head == null) {
head = cur;
tail = cur;
} else {
tail.next = cur;
cur.last = tail;
tail = cur;
}
size++;
}
public V pollHead() {
V ans = null;
if (head == null) {
return ans;
}
size--;
ans = head.value;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.last = null;
}
return ans;
}
public V pollTail() {
V ans = null;
if (head == null) {
return ans;
}
size--;
ans = tail.value;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
}
return ans;
}
public V peekHead() {
V ans = null;
if (head != null) {
ans = head.value;
}
return ans;
}
public V peekTail() {
V ans = null;
if (tail != null) {
ans = tail.value;
}
return ans;
}
}
public static void testDeque() {
MyDeque<Integer> myDeque = new MyDeque<>();
Deque<Integer> test = new LinkedList<>();
int testTime = 5000000;
int maxValue = 200000000;
System.out.println("测试开始！");
for (int i = 0; i < testTime; i++) {
if (myDeque.isEmpty() != test.isEmpty()) {
System.out.println("Oops!");
}
if (myDeque.size() != test.size()) {
System.out.println("Oops!");
}
double decide = Math.random();
if (decide < 0.33) {
int num = (int) (Math.random() * maxValue);
if (Math.random() < 0.5) {
myDeque.pushHead(num);
test.addFirst(num);
} else {
myDeque.pushTail(num);
test.addLast(num);
}
} else if (decide < 0.66) {
if (!myDeque.isEmpty()) {
int num1 = 0;
int num2 = 0;
if (Math.random() < 0.5) {
num1 = myDeque.pollHead();
num2 = test.pollFirst();
} else {
num1 = myDeque.pollTail();
num2 = test.pollLast();
}
if (num1 != num2) {
System.out.println("Oops!");
}
}
} else {
if (!myDeque.isEmpty()) {
int num1 = 0;
int num2 = 0;
if (Math.random() < 0.5) {
num1 = myDeque.peekHead();
num2 = test.peekFirst();
} else {
num1 = myDeque.peekTail();
num2 = test.peekLast();
}
if (num1 != num2) {
System.out.println("Oops!");
}
}
}
}
if (myDeque.size() != test.size()) {
System.out.println("Oops!");
}
while (!myDeque.isEmpty()) {
int num1 = myDeque.pollHead();
int num2 = test.pollFirst();
if (num1 != num2) {
System.out.println("Oops!");
}
}
System.out.println("测试结束！");
}
public static void main(String[] args) {
testDeque();
}
}
四、Leetcode:25. K 个一组翻转链表
一、题意描述
二、代码演示
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
//1.进行K个一组的头尾获取
ListNode start = head;
ListNode end = getKGroupEnd(start,k);
//2.此时如果链表大于等于k个元素，end不会为空，否则为空，则无需倒序直接返回原链表头节点
if(end == null){
return head;
}
//3.走到这里说明有K个元素及以上，所以就可以定义头节点，第一组倒序后，end节点即为头节点，进行保存，最后返回，需先赋值end，再倒序，因为倒序后end则指向了end.next了
head = end;
reverse(start,end);
//4.进行下一轮的K个一组的倒序链表遍历操作，需要定义第一组的最后一个节点,倒序后就是start节点
ListNode lastEnd = start;
while(lastEnd.next != null){
//这里重新定义下一组的start，我们在倒序函数中，最后定义了start的指向K+1元素节点，所以就可以直接赋值为lastEnd.next
start = lastEnd.next;
end = getKGroupEnd(start,k);
if(end == null){
return head;
}
reverse(start,end);
//下一组倒序后，接着就是要跟前一组连接起来。lastEnd时上组最后元素，需要指向下组的首元素，倒序后首元素为end . 然后接着重新指向下一组的最后元素，即start接着往后进行遍历
lastEnd.next = end;
lastEnd = start;
}
return head;
}
//返回K个一组的最后一个元素
public ListNode getKGroupEnd(ListNode start, int k){
while( --k > 0 && start != null){
start = start.next;
}
return start;
}
//K个一组倒序
public void reverse(ListNode start, ListNode end){
//重点：先把end节点往后移动一个元素，因为倒序时要让程序走到原始的end 把end指向前一个元素。 判断条件就时需要走到
//end后一个元素 再结束 ，如果走到end结束 end就没有走指针换序逻辑就跳出循环了。
end = end.next;
ListNode pre = null;
ListNode next = null;
ListNode cur = start;
while(cur != end){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
//最后start的指向也要调整，倒序后，start就跑到了原始end，接着就要指向end的下一个元素
start.next = end;
}
}三、核心思路
- 首先是可以看到需要进行倒序，并且还是一个K区间内的倒序，可以先分别定义好首尾元素，该区间的倒序函数 reverse，以及取到K区间的尾元素函数getKGroupEnd。
- 接着就是开始第一轮的K区间元素翻转，满足K个及以上，则可以确定翻转，然后要定义好头节点，因为第一轮翻转后，就是能将end元素确定为头节点，最后进行返回，若不到K个，则无需进行翻转，直接return end
- 如果有K个以上，说明就要进行遍历，这里依次遍历，要注意的是 上组尾元素laststart的next指向是下组首元素end，然后上组尾元素要往下组移动，移动到下组尾元素start，翻转后start就是尾元素，end就是首元素。
五、Leetcode: 2. 两数相加
一、题意描述
二、代码演示
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int len1 = listLength(l1);
int len2 = listLength(l2);
//1.求出长链表和短链表赋值l s
ListNode l = len1 >= len2 ? l1 : l2;
ListNode s = l == l1 ? l2 : l1;
//2.赋值临时变量进行长短链表遍历，因为我们把加后的结果都是覆盖到了长链表，所以最后return时要返回l 不能直接对l遍历指向
ListNode curL = l;
ListNode curS = s;
//3.这个last变量是用来表示最后遍历到最后一位时，curL指针指向null跳出如果存在前一位累加有进位，那就需要再接着指向一个新节点，值为1
//那么每次遍历都保持当前的curL，最后跳出时仍保留最后一个元素 所以可以进行next指向
ListNode last = curL;
//4.两数相加是否进位，初始值0，如5+5=10就进位，carry赋值1 如3=5=8没进位，carry=0
int carry = 0;
//5.记录当前位的值
int curNum = 0;
//6遍历阶段1：当短链表和长链表都有数时
while (curS != null) {
//当前值就等于两数和加进位，第一轮进位0
curNum = curL.val + curS.val + carry;
//模10得出当前位得值，直接覆盖长链表节点得值
curL.val = (curNum % 10);
//除以10看是否两数和累加有进位，有则1 无则0
carry = curNum / 10;
//保存当前链表节点。避免退出循环后，curL指向空了。 这里只有当两链表等长 curL才会为空 因为等长就跟cur遍历到最后一位
//然后最后接着又重新赋值指向next，此时就为空，那么提前保存了curL的last就不为空了
last = curL;
curL = curL.next;
curS = curS.next;
}
//遍历阶段2：短链表遍历完，接着剩下长链表单独遍历
while (curL != null) {
curNum = curL.val + carry;
curL.val = (curNum % 10);
carry = curNum / 10;
last = curL;
curL = curL.next;
}
//遍历阶段3：长链表也遍历完，前面跳出循环后last保存了curL的尾元素，如果前面遍历完后最后一位累计和大于等于10 则进位就是1，
//那么就需要在last节点后面在指向一个值为1的进位元素
if (carry != 0) {
last.next = new ListNode(1);
}
//7.最后返回结果都覆盖到了长链表 返回最先临时保存长链表头节点的变量l
return l;
}
// 求链表长度
public static int listLength(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
}三、核心思路
可以先定性确定两链表谁长谁短，然后往下开始按位遍历累加，这里因为存在两数相加大于等于10，则会需要进位+1，所以要设置一个进位数，初始值0，进位变量可以通过除以10，进行判断，只有两种结果0或1 ，进行进位累加。
然后遍历的时候需要分三种情况：
遍历阶段1：当短链表和长链表都有数时
遍历阶段2：短链表遍历完，接着剩下长链表单独遍历
遍历阶段3：长链表也遍历完，前面跳出循环后last保存了curL的尾元素，如果前面遍历完后最后一位累计和大于等于10 则进位就是1，那么就需要在last节点后面在指向一个值为1的进位元素