文章目录
- 1 链表反转
- 2 链表实现队列和栈
- 3 双端队列
- 4 K 个节点组内逆序调整
- 5 两个链表相加
- 6 两个有序链表的合并
- 7 合并 K 个有序链表
1 链表反转
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, next = null;
while (head != null) {
next = head.next;
head.next = pre;
head.last = next;
pre = head;
head = next;
}
return pre;
}
// for test
public static Node generateRandomLinkedList(int len, int value) {
int size = (int) (Math.random() * len) + 1;
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 List getLinkedListOriginOrder(Node head) {
List list = new ArrayList<>();
while (head != null) {
list.add(head.value);
head = head.next;
}
return list;
}
// 单链表对数器
public static boolean checkLinkedListReversed(List list, Node head) {
for (int i = list.size() - 1; i >= 0; i--) {
if (!list.get(i).equals(head.value)) {
return false;
}
head = head.next;
}
return true;
}
// for test
public static DoubleNode generateRandomDoubleList(int len, int value) {
int size = (int) (Math.random() * len) + 1;
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 getDoubleListOriginOrder(DoubleNode head) {
List list = new ArrayList<>();
while (head != null) {
list.add(head.value);
head = head.next;
}
return list;
}
// 双端链表对数器
public static boolean checkDoubleListReversed(List list, DoubleNode head) {
DoubleNode end = null;
for (int i = list.size() - 1; i >= 0; i--) {
if (!list.get(i).equals(head.value)) {
return false;
}
end = head;
head = head.next;
}
// 尾部
for (int i = 0; i < list.size(); i++) {
if (!list.get(i).equals(end.value)) {
return false;
}
end = end.last;
}
return true;
}
public static void main(String[] args) {
int len = 50;
int value = 100;
int testTime = 100000;
for (int i = 0; i < testTime; i++) {
Node node = generateRandomLinkedList(len, value);
List list1 = getLinkedListOriginOrder(node);
node = reverseLinkedList(node);
if (!checkLinkedListReversed(list1, node)) {
System.out.println("Oops1");
}
DoubleNode doubleNode = generateRandomDoubleList(len, value);
List list2 = getDoubleListOriginOrder(doubleNode);
doubleNode = reverseDoubleList(doubleNode);
if (!checkDoubleListReversed(list2, doubleNode)) {
System.out.println("Oops2");
}
}
}
}
2 链表实现队列和栈
public class Code02_LinkedListToQueueAndStack {
public static class Node {
public V value;
public Node next;
public Node(V v) {
value = v;
next = null;
}
}
public static class MyQueue {
Node head;
Node tail;
int size;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void offer(V value) {
Node cur = new Node<>(value);
if (tail == null) {
head = cur;
tail = cur;
} else {
tail.next = cur;
tail = cur;
}
size++;
}
public V poll() {
if (head == null) {
return null;
}
size--;
V value = head.value;
head = head.next;
// 最后一个节点
if (head == null) {
tail = null;
}
return value;
}
public V peek() {
return head == null ? null : head.value;
}
}
public static class MyStack {
Node head;
int size;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void push(V value) {
Node cur = new Node<>(value);
if (head == null) {
head = cur;
} else {
cur.next = head;
head = cur;
}
size++;
}
public V pop() {
if (head == null) {
return null;
}
size--;
V value = head.value;
head = head.next;
return value;
}
public V peek() {
return head == null ? null : head.value;
}
}
// 对数器测试
public static void testQueue() {
MyQueue myQueue = new MyQueue<>();
Queue testQueue = new LinkedList<>();
int testTime = 5000000;
int maxValue = 200000000;
System.out.println("队列测试开始！！");
for (int i = 0; i < testTime; i++) {
if (myQueue.size != testQueue.size()) {
System.out.println("Oops");
break;
}
double random = Math.random();
if (random < 0.33) {
int value = (int) (Math.random() * maxValue);
myQueue.offer(value);
testQueue.offer(value);
} else if (random < 0.66) {
if (!myQueue.isEmpty()) {
if (!myQueue.poll().equals(testQueue.poll())) {
System.out.println("Oops");
break;
}
}
} else {
if (!myQueue.isEmpty()) {
if (!myQueue.peek().equals(testQueue.peek())) {
System.out.println("Oops");
break;
}
}
}
}
if (myQueue.size != testQueue.size()) {
System.out.println("Oops");
return;
}
while (!myQueue.isEmpty()) {
if (!myQueue.poll().equals(testQueue.poll())) {
System.out.println("Oops");
break;
}
}
System.out.println("队列测试结束！！");
}
// 对数器测试
public static void testStack() {
MyStack myStack = new MyStack<>();
Stack testStack = new Stack<>();
int testTime = 5000000;
int maxValue = 200000000;
System.out.println("栈测试开始！！");
for (int i = 0; i < testTime; i++) {
if (myStack.size != testStack.size()) {
System.out.println("Oops");
break;
}
double random = Math.random();
if (random < 0.33) {
int value = (int) (Math.random() * maxValue);
myStack.push(value);
testStack.push(value);
} else if (random < 0.66) {
if (!myStack.isEmpty()) {
if (!myStack.pop().equals(testStack.pop())) {
System.out.println("Oops");
break;
}
}
} else {
if (!myStack.isEmpty()) {
if (!myStack.peek().equals(testStack.peek())) {
System.out.println("Oops");
break;
}
}
}
}
if (myStack.size != testStack.size()) {
System.out.println("Oops");
return;
}
while (!myStack.isEmpty()) {
if (!myStack.pop().equals(testStack.pop())) {
System.out.println("Oops");
break;
}
}
System.out.println("栈测试结束！！");
}
public static void main(String[] args) {
testQueue();
System.out.println("-----------------------------");
testStack();
}
}
3 双端队列
public class Code03_DoubleLinkedListToDeque {
public static class Node {
public V value;
public Node last;
public Node next;
public Node(V v) {
value = v;
last = null;
next = null;
}
}
public static class MyDeque {
Node head;
Node tail;
int size;
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void offerTail(V value) {
Node cur = new Node<>(value);
if (tail == null) {
head = cur;
tail = cur;
} else {
tail.next = cur;
cur.last = tail;
tail = cur;
}
size++;
}
public V pollHead() {
if (head == null) {
return null;
}
size--;
V value = head.value;
if (head == tail) {
head = null;
tail = null;
} else {
head = head.next;
head.last = null;
}
return value;
}
public V peekHead() {
return head == null ? null : head.value;
}
public void offerHead(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 V pollTail() {
if (tail == null) {
return null;
}
size--;
V value = tail.value;
if (head == tail) {
head = null;
tail = null;
} else {
tail = tail.last;
tail.next = null;
}
return value;
}
public V peekTail() {
return tail == null ? null : tail.value;
}
}
public static void testMyDeque() {
MyDeque myDeque = new MyDeque<>();
Deque testDeque = new LinkedList<>();
int testTime = 5000000;
int maxValue = 200000000;
System.out.println("双端测试开始！");
for (int i = 0; i < testTime; i++) {
if (myDeque.size != testDeque.size()) {
System.out.println("Oops");
break;
}
double random = Math.random();
if (random < 0.33) {
int value = (int) (Math.random() * maxValue);
double rate = Math.random();
if (rate < 0.5) {
myDeque.offerHead(value);
testDeque.offerFirst(value);
} else {
myDeque.offerTail(value);
testDeque.offerLast(value);
}
} else if (random < 0.66) {
if (!myDeque.isEmpty()) {
double rate = Math.random();
if (rate < 0.5) {
if (!myDeque.pollHead().equals(testDeque.pollFirst())) {
System.out.println("Oops");
break;
}
} else {
if (!myDeque.pollTail().equals(testDeque.pollLast())) {
System.out.println("Oops");
break;
}
}
}
} else {
if (!myDeque.isEmpty()) {
double rate = Math.random();
if (rate < 0.5) {
if (!myDeque.peekHead().equals(testDeque.peekFirst())) {
System.out.println("Oops");
break;
}
} else {
if (!myDeque.peekTail().equals(testDeque.peekLast())) {
System.out.println("Oops");
break;
}
}
}
}
}
if (myDeque.size != testDeque.size()) {
System.out.println("Oops");
return;
}
while (!myDeque.isEmpty()) {
if (!myDeque.pollHead().equals(testDeque.pollFirst())) {
System.out.println("Oops");
break;
}
}
System.out.println("双端测试结束！");
}
public static void main(String[] args) {
testMyDeque();
}
}
4 K 个节点组内逆序调整
public class Code04_ReverseNodesInKGroup {
public static class ListNode {
public int val;
public ListNode next;
}
public ListNode reverseKGroup(ListNode head, int k) {
ListNode start = head;
ListNode end = getKGroupEnd(head, k);
if (end == null) {
return head;
}
// 第一组
head = end;
reverse(start, end);
// 上一组结尾
ListNode lastEnd = start;
while (lastEnd.next != null) {
// 第二组开始节点
start = lastEnd.next;
end = getKGroupEnd(start, k);
// 不足 k 个直接返回
if (end == null) {
return head;
}
// 第n-1组
reverse(start, end);
// 上一组反转的节点指向当前组反转的起始节点
lastEnd.next = end;
// 更新最新的结束节点
lastEnd = start;
}
return head;
}
public ListNode getKGroupEnd(ListNode start, int k) {
while (k-- > 0 && start != null) {
start = start.next;
}
return start;
}
public void reverse(ListNode start, ListNode end) {
end = end.next;
ListNode pre = null;
ListNode cur = start;
ListNode next = null;
while (cur != end) {
next = cur.next;
// 反转
cur.next = pre;
pre = cur;
cur = next;
}
// 指向 end 的后一个节点
start.next = end;
}
}
5 两个链表相加
public class Code05_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 ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 分开链表和短链表
int len1 = getLength(l1);
int len2 = getLength(l2);
// l 长链表 s 短链表
ListNode l, s;
if (len1 >= len2) {
l = l1;
s = l2;
} else {
l = l2;
s = l1;
}
ListNode curL = l,
curS = s,
lastL = null;
// 进位
int carry = 0;
while (curS != null) {
int sum = curL.val + curS.val + carry;
curL.val = sum % 10;
// 更新进位
carry = sum / 10;
lastL = curL;
curL = curL.next;
curS = curS.next;
}
while (curL != null) {
int sum = curL.val + carry;
curL.val = sum % 10;
// 更新进位
carry = sum / 10;
lastL = curL;
curL = curL.next;
}
if (carry != 0) {
lastL.next = new ListNode(carry);
}
return l;
}
public int getLength(ListNode node) {
int len = 0;
while (node != null) {
len++;
node = node.next;
}
return len;
}
}
6 两个有序链表的合并
public class Code06_MergeTwoSortedLinkedList {
public static class ListNode {
public int val;
public ListNode next;
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null || list2 == null) {
return list1 == null ? list2 : list1;
}
// 找较小的作为返回的节点
ListNode head = list1.val < list2.val ? list1 : list2;
// 从下一个节点开始遍历
ListNode cur1 = head.next;
ListNode cur2 = head == list1 ? list2 : list1;
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 ? cur2 : cur1;
return head;
}
}
7 合并 K 个有序链表
public class Code01_MergeKSortedLists {
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; }
}
public static ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
// 使用小顶堆
PriorityQueue heap = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
// 将每个链表的都节点放入堆中
for (ListNode h : lists) {
if (h != null) {
heap.offer(h);
}
}
if (heap.isEmpty()) {
return null;
}
// 头节点
ListNode head = heap.poll();
if (head.next != null) {
heap.add(head.next);
}
ListNode pre = head;
// 非空
while (!heap.isEmpty()) {
ListNode cur = heap.poll();
if (cur.next != null) {
heap.add(cur.next);
}
pre.next = cur;
pre = cur;
}
return head;
}
}
