作者：dabing🧁

算法小白开始算法学习了，从最简单的开始，一步一步来，这里记录一下。笔记基于自己能看懂～～

Day4~~😶‍🌫️

这节课讲的是链表，题目也不简单，特别是 leetcode 的那三道题

对于链表的题，一定要返回 head 的，这个 head 是一个引用，这个引用能找到整条链表的数据。如果找不到这个数据就丢失了，没有引用，JVM 就会把它回收掉。

题目：

反转链表

用单链表实现队列结构

用单链表实现栈结构

用双链表实现双端队列（可头尾加减）

K 个一组翻转链表

两数相加

合并两个有序链表

# 1 - 链表 - 理论基础

转载自代码随想录，为了好复习直接拿过来了，这个网站也很适合练习算法推荐！！！！

首先我们要知道，什么是链表？

链表，是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是 数据域 ，一个是 指针域 (存放指向下一个节点的指针)。最后一个节点的指针域指向 null（空指针）

链表的入口节点称为头节点，即 head

链表1

优点：不需要使用地址连续的存储单元，插入和删除操作不需要移动元素，只需要修改指针即可。

缺点：失去顺序表可随机存取的优点（数组）

链表3

链表的分类：

单链表：就是上面那个

双链表：两个指针，一个指前一个，一个指后一个

链表2

循环链表：跟单链表的区别就是，最后一个节点的 next 不是指向 null，是指向头节点。就是成一个闭环的。

链表4

链表的定义：

我搁 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

队列 Queue 在 java.util 包中，有进、出、取三种方法。

栈结构，后进先出，那这个栈只需要一个指针，就一个 head 即可，进的时候，用 head 指向新的节点，出的时候用 head 处拿出来即可。

栈 Stack 在 java.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 - 用双链表实现双端队列

双端队列，头尾均可进出，用单链表无法实现

只能用双链表来实现：

双端队列 Deque 在 java.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;
	}

算法笔记

# 1 - 链表 - 理论基础

# 2 - 经典问题：反转链表

# 3 - 用单链表实现队列和栈结构

# 4 - 用双链表实现双端队列

# 5 - K 个一组翻转链表

# 6 - 两数相加

# 7 - 合并两个有序链表

03.二分法、动态数组、哈希表-新手

时间日记