作者:dabing🧁
算法小白开始算法学习了,从最简单的开始,一步一步来,这里记录一下。笔记基于自己能看懂~~
Day4~~😶🌫️
这节课讲的是链表,题目也不简单,特别是 leetcode 的那三道题
对于链表的题,一定要返回 head 的,这个 head 是一个引用,这个引用能找到整条链表的数据。如果找不到这个数据就丢失了,没有引用,JVM 就会把它回收掉。
题目:
反转链表
用单链表实现队列结构
用单链表实现栈结构
用双链表实现双端队列(可头尾加减)
K 个一组翻转链表
两数相加
合并两个有序链表
# 1 - 链表 - 理论基础
转载自代码随想录,为了好复习直接拿过来了,这个网站也很适合练习算法推荐!!!!
首先我们要知道,什么是链表?
链表,是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是 数据域
,一个是 指针域
(存放指向下一个节点的指针)。最后一个节点的指针域指向 null(空指针)
链表的入口节点称为头节点,即 head
优点:不需要使用地址连续的存储单元,插入和删除操作不需要移动元素,只需要修改指针即可。
缺点:失去顺序表可随机存取的优点(数组)
链表的分类:
单链表:就是上面那个
双链表:两个指针,一个指前一个,一个指后一个
循环链表:跟单链表的区别就是,最后一个节点的 next 不是指向 null,是指向头节点。就是成一个闭环的。
链表的定义:
我搁 LinkedList 里复制过来的,LinkedList 底层是 双向链表
,要求会手写
public class Node<E> { | |
E item; // 节点上存储的元素 | |
Node<E> next; // 指向后继节点 | |
Node<E> prev; // 指向前驱节点 | |
public Node(){} // 无参 | |
public Node(Node<E> prev, E element, Node<E> next) { // 双向链表构造器 | |
this.item = element; | |
this.next = next; | |
this.prev = prev; | |
} | |
} |
链表的操作:
删除:
增加:
# 2 - 经典问题:反转链表
leetcode 有一道这样的题目,反转链表 - 简单
给你单链表的头节点 head
,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
一定要搞清楚返回的 head 一定是变得,最终一定是返回最后的那个节点的。
拿出纸和笔,一个引用一个箭头→,画一下!

代码:带对数器测试
// 单链表 | |
public static class ListNode{ | |
public int value; | |
public ListNode next; | |
public ListNode(int data){ | |
value=data; | |
} | |
} | |
// 单链表反转 | |
public static ListNode reverseListNode(ListNode head){ | |
ListNode next=null; | |
ListNode pre=null; | |
while (head!=null){ | |
next=head.next; | |
head.next=pre; | |
pre=head; | |
head=next; | |
} | |
return pre; | |
} | |
//for test | |
// 随机单链表 | |
public static ListNode randomListNode(int maxLen, int maxVal){ | |
int size=(int)(Math.random()*(maxLen+1)); | |
if(size==0){ | |
return null; | |
} | |
ListNode head=new ListNode((int)(Math.random()*(maxVal+1))); | |
ListNode cur=head; | |
for (;size>1;size--){ | |
ListNode next = new ListNode((int)(Math.random()*(maxVal+1))); | |
cur.next=next; | |
cur=next; | |
} | |
return head; | |
} | |
//for test | |
// 用数组记录链表数据 | |
public static List<Integer> getLinkedListOriginOrder(ListNode head){ | |
List<Integer> list=new ArrayList<>(); | |
while (head != null){ | |
list.add(head.value); | |
head=head.next; | |
} | |
return list; | |
} | |
//for test | |
// 测试反转单链表是否正确 | |
public static boolean checkReverseListNode(List<Integer> origin,ListNode node){ | |
for(int i= origin.size()-1;i>=0;i--){ | |
if(!(origin.get(i).equals(node.value))){ | |
return false; | |
} | |
node=node.next; | |
} | |
return true; | |
} | |
public static void main(String[] args) { | |
int maxLen=10; | |
int maxVal=100; | |
int times=1000000; | |
for (int i = 0; i < times; i++) { | |
ListNode node = randomListNode(maxLen, maxVal); | |
List<Integer> list = getLinkedListOriginOrder(node); | |
ListNode node1 = reverseListNode(node);// 反转后 | |
if(!checkReverseListNode(list,node1)){ | |
System.out.println("Oops!"); | |
System.out.println("出错了!"); | |
break; | |
} | |
} | |
System.out.println("通过啦~"); | |
} |
双链表:
// 双链表 | |
public static class DoubleNode{ | |
public int value; | |
public DoubleNode next; | |
public DoubleNode last; | |
public DoubleNode(int data){ | |
value=data; | |
} | |
} | |
// 双链表反转 | |
public static DoubleNode reverseDoubleNode(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; | |
} |
# 3 - 用单链表实现队列和栈结构
队列结构,先进先出,那这个队列得有两个指针,一个指队列头 head 一个指队列尾 tail,头出尾进。这样就能保证后进后出。进的时候在 tail 处进,此时的 tail 是链表的 Head
队列 Queuejava.util
包中,有进、出、取三种方法。
栈结构,后进先出,那这个栈只需要一个指针,就一个 head 即可,进的时候,用 head 指向新的节点,出的时候用 head 处拿出来即可。
栈 Stackjava.util
包中,有进、出、取三种方法。
代码示例:
// 单链表 | |
public static class ListNode<E>{ | |
public E value; | |
public ListNode<E> next; | |
public ListNode(E data){ | |
value=data; | |
} | |
} | |
// 队列 | |
public static class MyQueue<E>{ | |
public int size; | |
public ListNode<E> head; | |
public ListNode<E> tail; | |
public MyQueue(){ | |
head=null; | |
tail=null; | |
size=0; | |
} | |
public int size(){ | |
return size; | |
} | |
// 判空 | |
public boolean isEmpty(){ | |
return size==0; | |
} | |
// 入队列 | |
public boolean offer(E e){ | |
ListNode<E> node=new ListNode<E>(e); | |
if(size==0){ | |
head=node; | |
tail=node; | |
}else { | |
tail.next=node; | |
tail=node; | |
} | |
size++; | |
return true; | |
} | |
// 出队列 从队尾 | |
public E poll(){ | |
E ans=null; | |
if(head!=null){ | |
ans=head.value; | |
head=head.next; | |
size--; | |
} | |
if(head==null){ | |
tail=null; | |
} | |
return ans; | |
} | |
// 取元素 不删除元素 | |
public E peek(){ | |
E ans=null; | |
if(head!=null){ | |
ans=head.value; | |
} | |
return ans; | |
} | |
} | |
// 栈 | |
public static class MyStack<V> { | |
private ListNode<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) { | |
ListNode<V> cur = new ListNode<>(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; | |
} | |
} |
# 4 - 用双链表实现双端队列
双端队列,头尾均可进出,用单链表无法实现
只能用双链表来实现:
双端队列 Dequejava.util
包中,包括头尾进,头尾出,头尾取等方法
代码示例:
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; | |
} | |
} |
# 5 - K 个一组翻转链表
力扣题目:K 个一组翻转链表 - 困难
题目:给你链表的头节点 head
,每 k
个节点一组进行翻转,请你返回修改后的链表。
k
是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
示例 1:
输入:head = [1,2,3,4,5], k = 2
输出:[2,1,4,3,5]
示例 2:
输入:head = [1,2,3,4,5], k = 3
输出:[3,2,1,4,5]
思路:
返回第 k 个结点 node:
反转:
返回下一个 k 结点反转
代码示例:
// 实现体 k 组反转 | |
public static ListNode reverseKGroup(ListNode head, int k) { | |
ListNode start = head; | |
ListNode end=getKGroupEnd(start,k); | |
if(end == null){ | |
return head; | |
} | |
// 第一组全凑齐,反转之后 head 就不变了 | |
head=end; | |
reverse(start,end); | |
// 上一组的结尾节点 | |
ListNode lastEnd = start; | |
while (lastEnd.next !=null){ | |
start=lastEnd.next; | |
end=getKGroupEnd(start,k); | |
// 如果凑不够一组,则直接返回 | |
if(end==null){ | |
return head; | |
} | |
// 凑够,反转 | |
reverse(start,end); | |
lastEnd.next=end; | |
lastEnd=start; | |
} | |
return head; | |
} | |
// 获取从 start 节点开始的第 k 个结点 | |
public static ListNode getKGroupEnd(ListNode start, int k) { | |
while(--k != 0 && start != null ){ | |
start=start.next; | |
} | |
return start; | |
} | |
// 链表反转 | |
public static 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; | |
} | |
start.next=end; | |
} |
# 6 - 两数相加
力扣题目:两数相加 - 中等
题目:
给你两个 非空
的链表,表示两个非负的整数。它们每位数字都是按照 逆序
的方式存储的,并且每个节点只能存储 一位
数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
实例:
输入:l1 = [2,4,3], l2 = [5,6,4]
输出:[7,0,8]
解释:342 + 465 = 807.
示例 2:
输入:l1 = [0], l2 = [0]
输出:[0]
示例 3:
输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出:[8,9,9,9,0,0,0,1]
这个题的意思就是跟平时的加法一样,只不过是逆着来,一样会进位,10 进制法。
因此要用一个临时变量来记住进位。如 5+8 进 1。
另一个点就是先确定哪条链表比较长,这样可以直接把数值修改到长链中去。返回的是长链的头结点。
注意一个结尾时如果要进位时,需要有个 last 来记录结尾处结点。
代码示例:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { | |
int len1=listLength(l1); | |
int len2=listLength(l2); | |
ListNode nodeL = len1 >= len2 ? l1 : l2; // 长链 | |
ListNode nodeS = nodeL==l1 ? l2 : l1 ;// 短链 | |
int carry = 0; | |
ListNode curS=nodeS;// 当前短链数据 | |
ListNode curL=nodeL;// 当前长链数据 | |
ListNode last=nodeL;// 记录最后结尾的结点(最后一位需进位时使用) | |
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 nodeL; | |
} | |
// 求链表长度 | |
public static int listLength(ListNode node){ | |
int len=0; | |
while (node != null){ | |
len++; | |
node=node.next; | |
} | |
return len; | |
} |
# 7 - 合并两个有序链表
力扣题目:合并两个有序链表 - 简单
题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
这个题就是遍历比较即可,一旦确定了头节点就不要改变了。有一条链结束了就不用继续比较了。
用两个指针,指定两条链表当前比较的结点,用一个指针 cur 指定已完成部分的当前结点。
代码示例:
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 cur = head; | |
ListNode cur1 = head.next; | |
ListNode cur2 = head==list1 ? list2 : list1 ; | |
while (cur1 != null && cur2!=null){ | |
if(cur1.val <= cur2.val){ | |
cur.next=cur1; | |
cur=cur1; | |
cur1=cur1.next; | |
}else { | |
cur.next=cur2; | |
cur=cur2; | |
cur2=cur2.next; | |
} | |
} | |
cur.next= cur1 == null ? cur2 : cur1; | |
return head; | |
} |