数据结构与算法拾遗三
单链表和双链表的定义
单链表：值，一条next指针
双链表：值，一条last指针，一条next指针
单链表反转
首先一个正常链表为
1->2->3->null。其中有一个head指针指向1，然后我们要设计一个方法传入head节点，调整链表的顺序为
3->2->1->null，并且让head指针指向3位置返回。
我们设计的方法如下
1、设置两个变量分别存放head的下一节点的值next
2、以及head的上一节点的值pre(方便来反转指针的指向)
伪代码为传入head
pre = null;
next = null;
然后当head不为空时
while(head != null) {
next = head.next;
head.next = pre//让head指针反转
pre = head; //更新pre的引用
head = next;//然后再将head移到下一节点的位置
}
//由于此处while循环的结束条件为head = null，而pre在最后刚好指向链表的尾部节点。
所以最后
return pre；
则完成链表的反转。
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;
}
双链表反转
这里以如下链表为例，
a的next指向b的next指向c的next指向null
c的pre指向b的pre指向a的pre指向null
其中head指向a
我们要设计一个函数让
c的next指向b的next指向a的next指向null
a的pre指向b的pre指向c的pre指向null
并且让 head指向C
伪代码如下：
还是写一个方法传入head
设置两个中间变量
DoubleNode next = null;
DoubleNode pre = null;
while(head != null) {
next = head.next;
head.last = 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;
}
带对数器的实现方式如下：
public class 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;
}
public static Node testReverseLinkedList(Node head) {
if (head == null) {
return null;
}
ArrayList<Node> list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
list.get(0).next = null;
int N = list.size();
for (int i = 1; i < N; i++) {
list.get(i).next = list.get(i - 1);
}
return list.get(N - 1);
}
public static DoubleNode testReverseDoubleList(DoubleNode head) {
if (head == null) {
return null;
}
ArrayList<DoubleNode> list = new ArrayList<>();
while (head != null) {
list.add(head);
head = head.next;
}
list.get(0).next = null;
DoubleNode pre = list.get(0);
int N = list.size();
for (int i = 1; i < N; i++) {
DoubleNode cur = list.get(i);
cur.last = null;
cur.next = pre;
pre.last = cur;
pre = cur;
}
return list.get(N - 1);
}
// for test
public static Node generateRandomLinkedList(int len, int value) {
int size = (int) (Math.random() * (len + 1));
if (size == 0) {
return null;
}
size--;
Node head = new Node((int) (Math.random() * (value + 1)));
Node pre = head;
while (size != 0) {
Node cur = new Node((int) (Math.random() * (value + 1)));
pre.next = cur;
pre = cur;
size--;
}
return head;
}
// for test
public static DoubleNode generateRandomDoubleList(int len, int value) {
int size = (int) (Math.random() * (len + 1));
if (size == 0) {
return null;
}
size--;
DoubleNode head = new DoubleNode((int) (Math.random() * (value + 1)));
DoubleNode pre = head;
while (size != 0) {
DoubleNode cur = new DoubleNode((int) (Math.random() * (value + 1)));
pre.next = cur;
cur.last = pre;
pre = cur;
size--;
}
return head;
}
// for test
public static List<Integer> getLinkedListOriginOrder(Node head) {
List<Integer> ans = new ArrayList<>();
while (head != null) {
ans.add(head.value);
head = head.next;
}
return ans;
}
// for test
public static boolean checkLinkedListReverse(List<Integer> origin, Node head) {
for (int i = origin.size() - 1; i >= 0; i--) {
if (!origin.get(i).equals(head.value)) {
return false;
}
head = head.next;
}
return true;
}
// for test
public static List<Integer> getDoubleListOriginOrder(DoubleNode head) {
List<Integer> ans = new ArrayList<>();
while (head != null) {
ans.add(head.value);
head = head.next;
}
return ans;
}
// for test
public static boolean checkDoubleListReverse(List<Integer> origin, DoubleNode head) {
DoubleNode end = null;
for (int i = origin.size() - 1; i >= 0; i--) {
if (!origin.get(i).equals(head.value)) {
return false;
}
end = head;
head = head.next;
}
for (int i = 0; i < origin.size(); i++) {
if (!origin.get(i).equals(end.value)) {
return false;
}
end = end.last;
}
return true;
}
// for test
public static void main(String[] args) {
int len = 50;
int value = 100;
int testTime = 100000;
System.out.println("test begin!");
for (int i = 0; i < testTime; i++) {
Node node1 = generateRandomLinkedList(len, value);
List<Integer> list1 = getLinkedListOriginOrder(node1);
node1 = reverseLinkedList(node1);
if (!checkLinkedListReverse(list1, node1)) {
System.out.println("Oops1!");
}
Node node2 = generateRandomLinkedList(len, value);
List<Integer> list2 = getLinkedListOriginOrder(node2);
node2 = testReverseLinkedList(node2);
if (!checkLinkedListReverse(list2, node2)) {
System.out.println("Oops2!");
}
DoubleNode node3 = generateRandomDoubleList(len, value);
List<Integer> list3 = getDoubleListOriginOrder(node3);
node3 = reverseDoubleList(node3);
if (!checkDoubleListReverse(list3, node3)) {
System.out.println("Oops3!");
}
DoubleNode node4 = generateRandomDoubleList(len, value);
List<Integer> list4 = getDoubleListOriginOrder(node4);
node4 = reverseDoubleList(node4);
if (!checkDoubleListReverse(list4, node4)) {
System.out.println("Oops4!");
}
}
System.out.println("test finish!");
}
}
单链表实现任意数据类型的队列和栈
队列实现
准备三个变量链表头和链表尾以及一个size变量。
队列的offer操作
传入一个值进来
首先通过链表把这个节点给建立出来
Node cur = new Node(value)
先判断尾是否为空，为空就代表现在的链表里面一个元素也没有，此时将头指针和尾指针都指向value
if(tail == null) {
head = cur;
tail = cur;
}
如果不是空的情况(每加一个节点都从尾巴加)
else {
cur = tail.next ;
//然后将尾巴跳到当前节点的位置
tail = cur;
}
队列的offer操作
弹出从头部弹出
public V poll() {
V value = null;
if(head ! =null) {
ans = head.value
head = head.next
size–;
}
//如果所有的数据都弹出队列了，那么要尾巴和头都保持一致为null，这么做的目的是防止有脏数据再下一次入队的时候产生
if(head == null) {
tail = null;
}
return ans;
}
//取队头元素不取出
public V peek() {
V ans = null;
if(head != null) {
ans = head.value;
}
return ans;
}
栈实现
首先准备两个变量分别是 链表头和size变量
private Node head;
private int size;
//构造函数初始化
public MyStack() {
head = null;
size = 0;
}
//push方法
public void push (V value) {
//首先建立一个节点
Node cur = new Node;
//判断当前链表是否为空
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 ;
}
如下代码是整体的实现再加上对数器校验：
package class04;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class 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();
}
}
用双向链表实现双端队列（可从头部加减及尾部加减）
首先定义一个双向链表
public class Node {
public V value;
public Node last;
public Node next;
public Node(V v) {
this.value = v;
last = null;
next = null;
}
}
首先双端队列的实现我们定义三个变量，分别是链表头，链表尾和size；
private Node head;
private Node tail;
public MyDequeue() {
head = null;
tail = null;
size = 0;
}
public void pushHead(V value) {
Node 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 cur = new Node<>(value);
if(head == null) {
head = cur;
tail = cur;
}
else {
cur = tail.next;
cur.last = tai;l
tail = cur;
}
size ++;
}
从头部弹出 pollHead
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;
}
}
public V pollTail () {
V ans = null;
if(tail == null) {
return ans;
}
size --;
ans = tail.value;
if(head == tail) {
head = null;
tail = null;
}
else {
tail = tail.last;
tail.next =null;
}
return ans ;
}
整体代码如下（带对数器）:
public class 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();
}
}
K个节点的组内逆序调整
小组内不够K的长度的不调转顺序
测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
/**
* 传入一个开始节点及k的值，返回这一组的最后一个节点
*
* @param start
* @param k
* @return
*/
public static ListNode getKGroup(ListNode start, int k) {
while (--k != 0 && start != null) {
start = start.next;
}
return start;
}
/**
* 将链表反转并将反转之后的start指向end节点的后一个
* 1->2-3->4 k = 3
* 反转成3->2->1->4
* @param start
* @param end
*/
public static void reverse(ListNode start, ListNode 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.next = end;
}
/**
* 根据k的数量来分组转换整个链表
* @param start
* @param k
* @return
*/
public static ListNode reverseKGroup(ListNode start, int k) {
ListNode head = start;
ListNode tempEnd = getKGroup(start,k);
if(tempEnd == null) {
return head;
}
head = tempEnd;
reverse(start,tempEnd);//第一次结束
ListNode lastEnd = start;
while(lastEnd.next != null) {
start = lastEnd.next;
tempEnd = getKGroup(start,k);
if(tempEnd == null) {
return head;
}
reverse(start,tempEnd);
lastEnd.next = tempEnd;
lastEnd = start;
}
return head;
}
两个链表相加
https://leetcode.cn/problems/add-two-numbers/
我们把这个链表拆分为三种情况
首先将两个链表分一个长链表以及一个短链表
分以下情况
1、对应位置长链表和短链表都有值的情况（短链表当前位置的值加上长链表当前位置的值再加上进位信息）
2、对应位置只有长链表有值短链表没有值（长链表当前位置的值加上进位信息）
3、对应位置长链表没值并且短链表也没有值，但是进位信息有值，此时需要新加一个节点在最后
代码如下：
public class AddTwoNumbers {
// 不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
public static ListNode addTwoNumbers(ListNode head1, ListNode head2) {
int len1 = listLength(head1);
int len2 = listLength(head2);
ListNode l = len1 >= len2 ? head1 : head2;
ListNode s = l == head1 ? head2 : head1;
ListNode curL = l;
ListNode curS = s;
ListNode last = curL;//此处last指针的目的是为了记录在长链表指针跳转下一个位置时的值，为了预防第三种情况找不到长链表的上一值是啥
int carry = 0;
int curNum = 0;
while (curS != null) {
curNum = curL.val + curS.val + carry;
curL.val = (curNum % 10);
carry = curNum / 10;
last = curL;
curL = curL.next;
curS = curS.next;
}
while (curL != null) {
curNum = curL.val + carry;
curL.val = (curNum % 10);
carry = curNum / 10;
last = curL;
curL = curL.next;
}
if (carry != 0) {
last.next = new ListNode(1);
}
return l;
}
// 求链表长度
public static int listLength(ListNode head) {
int len = 0;
while (head != null) {
len++;
head = head.next;
}
return len;
}
}
两个有序链表合并
https://leetcode.cn/problems/merge-two-sorted-lists/
首先找两个链表里面最小的头
ListNode head = head1.val <= head2.val ? head1 : head2;
然后定义两个变量分别指向小头和大头
ListNode cur1 = head.next;//已经确定了第一个小头了此处指向下一个
ListNode cur2 = head == head1? head2:head1;
再准备一个中间变量pre
ListNode pre = head;
谁小指谁
具体代码如下：
public class MergeTwoSortedLinkedList {
public static class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
if (head1 == null || head2 == null) {
return head1 == null ? head2 : head1;
}
ListNode head = head1.val <= head2.val ? head1 : head2;
ListNode cur1 = head.next;
ListNode cur2 = head == head1 ? head2 : head1;
ListNode pre = head;
while (cur1 != null && cur2 != null) {
if (cur1.val <= cur2.val) {
pre.next = cur1;
cur1 = cur1.next;
} else {
pre.next = cur2;
cur2 = cur2.next;
}
pre = pre.next;
}
pre.next = cur1 != null ? cur1 : cur2;
return head;
}
}
