链表【左程云:Java】

一、单链表

1.单链表的节点结构

 2.反转单向和双向链表

2.1 反转单向

package leetcode.链表;


/**
 * @author lin
 * @creat 2022--12--12:50
 *
 * https://leetcode.cn/problems/reverse-linked-list/
 */
public class $_206反转链表 {
    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 ListNode reverse(ListNode pre,ListNode cur){
        if (cur==null){//终止遍历的条件就是cur==null
            return pre;//返回新链表的头节点
        }
        ListNode temp=null;
        temp=cur.next;//记录下一个节点的位置
        //改变链表的方向
        cur.next=pre;
        //更新pre和cur的位置
        //pre=cur;
        //cur=temp;
        return reverse(cur,temp);
    }

    public ListNode reverseList(ListNode head) {
        //这里为什么传入的是null,head
        //因为初始化pre是指向头节点的前面,cur指向头节点
        return reverse(null,head);
    }

    //方法二:使用双指针
    public ListNode reverseList2(ListNode head){
        ListNode pre=null;
        ListNode cur=head;
        ListNode temp=cur.next;
        while (cur!=null){
            temp=cur.next;//保存下一个节点,要不然找不到
            //将链表方向进行改变
            cur.next=pre;
            //将cur赋值给pre
            pre=cur;
            //将temp赋值给cur
            cur=temp;
        }
        //返回新链表的头节点,此时cur指向null
        return pre;
    }

}


2.2反转双向链表

/**
 * P104 T31 双向链表 相当于简化版的Linkedlist
 * 主要实现了从表头,表尾插入一个结点,在指定结点之前或之后插入一个结点,
 * 从表头,表尾删除一个结点,删除指定结点 
 * 指定索引返回结点
 * 
 * 
 * 测试通过;
 * 
 * @author he
 *
 */
class DoubleNode<T> {
	private int N;// 记录元素个数
	private Node first;// 头结点
	private Node last;// 尾结点
 
	private class Node {
		T item;
		Node perv;// 前一个结点
		Node next;// 后一个结点
 
		@Override
		public String toString() {
			// TODO Auto-generated method stub
			return item + "";
		}
	}
 
	// 根据索引获取结点
	public Node getNode(int index) {
		if (index < 0 || index >= N) {
			throw new IndexOutOfBoundsException();
		}
 
		Node node = first;
 
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
 
		return node;
	}
 
	// 判断是否为空
	public boolean isEmpty() {
		return N == 0;
	}
 
	// 元素个数
	public int size() {
		return N;
	}
 
	// 表头插入结点
	public void pushFirst(T item) {
 
		Node oldfirst = first;
		first = new Node();
		first.item = item;
		if (isEmpty()) {
			last = first;
		} else {
			first.next = oldfirst;
			oldfirst.perv = first;
		}
		N++;
	}
 
	// 在指定结点前添加新结点
	public void pushBefore(Node newnode, Node node) {
		newnode.next = node;
		newnode.perv = node.perv;
		newnode.next.perv = newnode;
		// 防止在头结点前面插入新结点
		if (newnode.perv != null) {
			newnode.perv.next = newnode;
		}
		N++;
	}
 
	// 在指定索引前插入新结点
	public void pushBeforeOfIndex(T item, int index) {
		Node node = getNode(index);
		Node newnode = new Node();
		newnode.item = item;
		pushBefore(newnode, node);
	}
 
	// 从表尾插入
	public void pushLast(T item) {
		Node oldlast = last;
		last = new Node();
		last.item = item;
		last.next = null;
		if (isEmpty()) {
			first = last;
		} else {
			oldlast.next = last;
			last.perv = oldlast;
		}
		N++;
	}
 
	// 在指定结点后添加新结点
	public void pushAfter(Node newnode, Node node) {
		newnode.perv = node;
		newnode.next = node.next;
		newnode.perv.next = newnode;
		// 防止在尾结点之后插入新结点
		if (newnode.next != null) {
			newnode.next.perv = newnode;
		}
		N++;
	}
 
	// 在指定索引之后添加结点
	public void pushAfterOfIndex(T item, int index) {
		Node newnode = new Node();
		newnode.item = item;
		Node node = getNode(index);
		pushAfter(newnode, node);
 
	}
 
	// 从表头删除一个结点
	public void popFirst() {
		first = first.next;
		if (first != null) {
			first.perv = null;
		}
		N--;
	}
 
	// 从表为删除一个结点
	public void popLast() {
		last.perv.next = null;
		last.perv = null;
		N--;
	}
 
	// 删除指定的结点
	public void pop(Node node) {
 
		node.perv.next = node.next;
		node.next.perv = node.perv;
		node.perv = null;
		node.next = null;
		N--;
	}
 
	// 删除指定索引的结点
	public void popOfIndex(int index) {
		if (index == 0) {
			popFirst();
		} else if (index == N - 1) {
			popLast();
		} else {
			Node node = getNode(index);
			pop(node);
		}
 
	}
 
	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		Node node = first;
		for (int i = 0; i < N; i++) {
			sb.append("[");
			sb.append(node);
			sb.append("]");
			sb.append(",");
			node = node.next;
		}
		return sb.toString();
	}
 
}
 
}

3.练习

1.打印两个有序的链表的公共部分

 2.思路

1.都从0开始

2.谁小谁移动,相等打印

3.相等后两个一起移动

 4.面试中技巧

 5.判断是否为会回文结构

 

 

 1.快慢指针

 在链表中,维持两个指针,跳跃速度不同(A跳一步,B就跳两步)。当B到达终点的时候,A到达中间位置。

2.思路

3.代码实现【不使用额外空间】

	// need O(1) extra space
	public static boolean isPalindrome3(Node head) {
		if (head == null || head.next == null) {
			return true;
		}
		Node n1 = head;//慢指针
		Node n2 = head;//快指针
		//快慢指针找末尾和中点
		while (n2.next != null && n2.next.next != null) { // find mid node
			n1 = n1.next; // n1 -> mid
			n2 = n2.next.next; // n2 -> end
		}
		n2 = n1.next; // n2 -> right part first node
		n1.next = null; // mid.next -> null
		Node n3 = null;//用于记录n2原本的下一个node
		//右半部分逆序
		while (n2 != null) { // right part convert
			n3 = n2.next; // n3 -> save next node,保留未改变的链表
			n2.next = n1; // next of right node convert,改变链表指向
			//n1,n2两个指针完成改变指向操作后,同时右移,准备下一个元素的链表指向逆序
			n1 = n2; // n1 move
			n2 = n3; // n2 move
		}
		n3 = n1; // n3 -> save last node
		n2 = head;// n2 -> left first node
		boolean res = true;
		while (n1 != null && n2 != null) { // check palindrome
			//每走一步,都验证
			if (n1.value != n2.value) {
				res = false;
				break;
			}
			//n1,n2从中间开始走
			n1 = n1.next; // left to mid
			n2 = n2.next; // right to mid
		}
		n1 = n3.next;
		n3.next = null;
		//最后将逆序的链表变回来
		while (n1 != null) { // recover list
			n2 = n1.next;
			n1.next = n3;
			n3 = n1;
			n1 = n2;
		}
		return res;
	}

6.按某值划分单向链表

 1.思路

 2.代码实现

	public static Node listPartition2(Node head, int pivot) {
		Node sH = null; // small head
		Node sT = null; // small tail
		Node eH = null; // equal head
		Node eT = null; // equal tail
		Node bH = null; // big head
		Node bT = null; // big tail
		Node next = null; // save next node
		// every node distributed to three lists
		while (head != null) {
			next = head.next;
			head.next = null;
			if (head.value < pivot) {
				if (sH == null) {
					sH = head;
					sT = head;
				} else {
					sT.next = head;
					sT = head;
				}
			} else if (head.value == pivot) {
				if (eH == null) {
					eH = head;
					eT = head;
				} else {
					eT.next = head;
					eT = head;
				}
			} else {
				if (bH == null) {
					bH = head;
					bT = head;
				} else {
					bT.next = head;
					bT = head;
				}
			}
			head = next;
		}
		// small and equal reconnect
		if (sT != null) {
			sT.next = eH;
			eT = eT == null ? sT : eT;
		}
		// all reconnect
		if (eT != null) {
			eT.next = bH;
		}
		return sH != null ? sH : eH != null ? eH : bH;
	}

7.复制含有随机指针节点的链表

做法1:第一次遍历旧链表,使用哈希map,key为旧链表,value为新链表,新链表只是单纯地串起来并拷贝int value值,rand没有设置;第二次遍历旧链表,调用key-value,设置rand node。

做法2:第一次遍历旧链表,不用哈希map,在旧map中,插入克隆node,拷贝int value值;第二次遍历链表,一对一对处理,设置rand node;第三次遍历,把旧节点删除。省去了hashmap的空间。

 

8.两个单链表相交

思路

情况1:两个链表都无环

情况1:2个链表都是无环,只可能是2条线,或者y型线,不可能是x型,x型就是节点处next指针指向2个地方,这是不可能的。2个链表如果相交,那么他们end端一定是地址一样的,2个链表都遍历。如果相交,要找到节点处,长的列表先走len(long)-len(short)步,然后一起走,一定会在交点处相遇。

情况1:做题步骤

1.先对两个链表分别求出end节点和length

2.然后判断两个链表的end是否是指向同一个地址

3.如果是指向同一个地址,则先让长链表走【length长-length短】步,然后再让长的链表和短链表同时继续走。

情况1: 代码实现

	//两个有环链表。返回第一个相交节点,如果不想交返回null
	//loop1,loop2分别为2个链表的环入口处节点
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		if (loop1 == loop2) {//如果入环节点相同,是情况3-2
			cur1 = head1;
			cur2 = head2;
            //此时n:表示链表1长度减去链表2长度的值
			int n = 0;
			while (cur1 != loop1) {
				n++;
				cur1 = cur1.next;
			}
			while (cur2 != loop2) {
				n--;
				cur2 = cur2.next;
			}
            //谁长,谁的头变成cur1
			cur1 = n > 0 ? head1 : head2;
            //谁短,谁的头变成cur2
			cur2 = cur1 == head1 ? head2 : head1;
            //取绝对值
			n = Math.abs(n);
            //长链表先走【长链表-短链表】步
			while (n != 0) {
				n--;
				cur1 = cur1.next;
			}
            //然后长链表和短链表再一起走
			while (cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
            //再一次相遇表示相交节点
			return cur1;
		} else {//如果入环节点不同,是情况3-1或3-3
			cur1 = loop1.next;
			while (cur1 != loop1) {
				if (cur1 == loop2) {
					return loop1;//情况3-3
				}
				cur1 = cur1.next;
			}
			return null;//情况3-1
		}
	}

情况二:一个链表有环,一个链表无环

一个为无环,一个有环,那么必然不想交;【只要一个链表有环,则另一个链表接进去后,环也会成为它后面的一部分,所以必定有环】

情况三:两个链表都有环

情况3:2个都是有环,又分3种情况:
情况3-1:2个不同的有环;
情况3-2:入环节点是同一个,最好判断,分别找到入环节点,如果入环节点不同就是情况3-1或者3-3,如果入环节点相同,就使用上面的无环代码去找相交节点;
情况3-3:入环节点不是同一个;让loop1继续走,在走回自己之前,判断会不会遇到loop2这个入口节点,遇到就是情况3-3,没有就是情况3-1;

 

	//两个有环链表。返回第一个相交节点,如果不想交返回null
	//loop1,loop2分别为2个链表的环入口处节点
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		if (loop1 == loop2) {//如果入环节点相同,是情况3-2
			cur1 = head1;
			cur2 = head2;
			int n = 0;
			while (cur1 != loop1) {
				n++;
				cur1 = cur1.next;
			}
			while (cur2 != loop2) {
				n--;
				cur2 = cur2.next;
			}
			cur1 = n > 0 ? head1 : head2;
			cur2 = cur1 == head1 ? head2 : head1;
			n = Math.abs(n);
			while (n != 0) {
				n--;
				cur1 = cur1.next;
			}
			while (cur1 != cur2) {
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
			return cur1;
		} else {//如果入环节点不同,是情况3-1或3-3
			cur1 = loop1.next;
			while (cur1 != loop1) {
				if (cur1 == loop2) {
					return loop1;//情况3-3
				}
				cur1 = cur1.next;
			}
			return null;//情况3-1
		}
	}

9.判断链表中是否有环

如果快慢指针的next不会指向null,则表示有环

法一:使用额外空间---哈希表

遍历链表依次存入哈希表,直到节点已经出现在哈希表

 法二:不使用额外空间----快慢指针

快慢指针从同一个起点出发,快指针走2步,慢指针走1步

查看入环节点 

 如果链表中有环,快慢指针肯定会相遇,当相遇的时候,快指针回到起点,慢指针在原地,一起往前走每次走一步,再次相遇既是环入口节点

 

	//获取环的入口
	public static Node getLoopNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		Node n1 = head.next; // n1 -> slow
		Node n2 = head.next.next; // n2 -> fast
		while (n1 != n2) {
			//判断快指针是否走完
			if (n2.next == null || n2.next.next == null) {
				return null;
			}
			n2 = n2.next.next;
			n1 = n1.next;
		}
		n2 = head; // n2 -> walk again from head
		while (n1 != n2) {
			n1 = n1.next;
			n2 = n2.next;
		}
        //再一次相遇的时候,就是入环节点
		return n1;
	}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/6444.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于VHDL语言的汽车测速系统设计_kaic

摘 要 汽车是现代交通工具。车速是一项至关重要的指标。既影响着汽车运输的生产率,又关乎着汽车行驶有没有超速违章&#xff0c;还影响着汽车行驶时人们的人身安全。而伴随着我国国民的安全防范意识的逐步增强&#xff0c;人们也开始越来越关心因为汽车的超速而带来的极其严重…

一份sql笔试

1、 select substr(time,1,10),count(order_id),count(distinct passenger_id) from order where substr(time,1,7)2023-08 group by substr(time,1,10) order by substr(time,1,10);2、 select city_id from (select * from order where substr(time,1,7) 2022-08) t1 left j…

【新2023Q2押题JAVA】华为OD机试 - 打折买水果

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:打折买水果 题目 有 m m m…

Spring之属性填充

Spring给属性的方式一般有三种 1、通过在属性的添加Autowired注解 Component public class UserService {Autowiredprivate OrderService orderService;public void setOrderService(OrderService orderService) {this.orderService orderService;}public OrderService getO…

b站第一,Python自动化测试实战详细教学,3天教你学会自动化测试

目录 简介 Python自动化测试概述 Python自动化测试目标 Python自动化测试流程 1. 测试计划和设计 2. 测试脚本开发 3. 测试执行和管理 4. 测试维护和优化 Python自动化测试最佳实践 Python自动化测试工具和框架 结论 简介 自动化测试是软件开发过程中一个必不可少的…

【Django 网页Web开发】22. 实战项目:简单的文件上传(15)(保姆级图文)

目录实现效果1. url.py2. upload_list.html3. upload.py总结欢迎关注 『Django 网页Web开发』 系列&#xff0c;持续更新中 欢迎关注 『Django 网页Web开发』 系列&#xff0c;持续更新中 实现效果 1. url.py path(upload/list/, upload.upload_list),2. upload_list.html {% e…

Python中进程和线程到底有什么区别?

人生苦短&#xff0c;我用python python 安装包资料:点击此处跳转文末名片获取 一、进程和线程的关系 线程与进程的区别可以归纳为以下4点&#xff1a; 地址空间和其它资源&#xff08;如打开文件&#xff09;&#xff1a;进程间相互独立&#xff0c;同一进程的各线程间共享。…

操作系统(2.6)--进程通信

进程通信是指进程之间的信息交换。 在进程之间要传送大量数据时&#xff0c;应当利用OS提供的高级通信工具&#xff0c;该工具最主要的特点是: (1)使用方便。OS隐藏了实现进程通信的具体细节&#xff0c;向用户提供了一组用于实现高级通信的命令(原语)&#xff0c;用户可方便地…

ThreeJS-太阳球围绕旋转(二十四)

数学小知识&#xff1a; 我们根据旋转角度θ可以计算出任意时刻的x,y sinθ y0/r; 因此y0 rsinθ, cosθ x0/r,因此x0 rcosθ, 小拓展&#xff1a; y0^ x0^ - r^2*sinθ^2 r^2*cosθ^2 r^2*(sinθ^2 cosθ^2) r^2; 这也是为什么在极坐标方程中 y0 rsinθ, x0 rcos…

15_I.MX6ULL_LCD显示原理

目录 LCD简介 分辨率 像素格式 LCD屏幕接口 LCD时间参数 RGB LCD屏幕时序 像素时钟 显存 LCD简介 LCD全称是Liquid Crystal Display,也就是液晶显示器,是现在最常用到的显示器,手机、电脑、各种人机交互设备等基本都用到了LCD,最常见就是手机和电脑显示器了。LCD的构造…

帮公司面试了一个32岁的程序员,只因这一个细节,被我一眼看穿是培训班出来的,没啥工作经验...

首先&#xff0c;我说一句&#xff1a;培训出来的&#xff0c;优秀学员大有人在&#xff0c;我不希望因为带着培训的标签而无法达到用人单位和候选人的双向匹配&#xff0c;是非常遗憾的事情。 最近&#xff0c;在网上看到这样一个留言&#xff0c;引发了程序员这个圈子不少的…

ChatGPT全球大封号!数10万企业停摆:第一批玩AI的人,被AI给玩了

观点| Mr.K 主笔| Wendy.L 编辑| Emma来源| 技术领导力(ID&#xff1a;jishulingdaoli)3月31日&#xff0c;Open AI就开始无征兆的进行全球大封号&#xff0c;其中亚洲是重灾区&#xff0c;官方没有给出任何声明&#xff0c;具体原因不得而知。并且暂停了这些地区新账号的注…

【从零开始学习 UVM】6.4、UVM 激励产生 —— uvm_do 宏详解

请注意,start方法的call_pre_post字段设置为0,这意味着在使用这些序列宏时,序列的pre_body和post_body方法将永远不会被调用。否则,执行流程与通过start方法执行序列时类似。 文章目录 执行序列宏介绍Example执行序列宏介绍 使用序列宏的优点是可以使用内联约束,但是您失…

实验一 跨VLAN访问

目录 一、按照拓扑图配置VLAN&#xff0c;并实现跨VLAN间的访问。 二、实验环境 三、实验步骤 一、按照拓扑图配置VLAN&#xff0c;并实现跨VLAN间的访问。 1、配置好交换机的VLAN和各个终端的地址&#xff0c;实现各个VLAN内能连通。 2、开启两个交换机的VTY连接&#xff0…

基于STM32F103——XGZP6847D压力传感器+串口打印

基于STM32F103—XGZP6847D压力传感器串口打印基本介绍概述产品特点引脚的连接 (IIC通信)名称含义的介绍I2C通信协议 (设备地址是 0x6D)寄存器描述工作模式寄存器Reg0x30&#xff08;测量命令寄存器&#xff09;Reg0xA5Reg0xA6模式说明组合数据采集模式休眠数据采集模式代码编写…

MyBatisPlus

今日目标基于MyBatisPlus完成标准Dao的增删改查功能掌握MyBatisPlus中的分页及条件查询构建掌握主键ID的生成策略了解MyBatisPlus的代码生成器1&#xff0c;MyBatisPlus入门案例与简介这一节我们来学习下MyBatisPlus的入门案例与简介&#xff0c;这个和其他课程都不太一样&…

[CF复盘] Codeforces Round 863 (Div. 3) 20230404

[TOC]([CF复盘] Codeforces Round 863 (Div. 3) 20230404 ) 一、本周周赛总结 做到E&#xff0c;但DE都TLE&#xff0c;很难受。 A 贪心。 B 坐标运算。 C 贪心构造。 D 分治DFS。 E 九进制模拟。 二、 A. Insert Digit 链接: A. Insert Digit 1. 题目描述 2. 思路分析…

skimage.filters.apply_hysteresis_threshold详解

本文内容均参考scipy1.9.1scipy1.9.1scipy1.9.1版本的源码&#xff0c;若有任何不当欢迎指出 我们截取官方注释如下&#xff1a; def apply_hysteresis_threshold(image, low, high):"""Apply hysteresis thresholding to image.This algorithm finds regions …

RabbitMQ中TTL

目录一、TTL1.控制后台演示消息过期2.代码实现2.1 队列统一过期2.2 消息过期一、TTL TTL 全称 Time To Live&#xff08;存活时间/过期时间&#xff09;。 当消息到达存活时间后&#xff0c;还没有被消费&#xff0c;会被自动清除。 RabbitMQ可以对消息设置过期时间&#xff0…

QT与Halcon联编应用开发-设置软件图标Icon

VS+Qt应用开发-设置软件图标 设置软件exe图标设置运行时标题栏和任务栏图标默认的Qt是没有图标的,如下图所示,可以在Qt应用程序发布时和应用程序运行时给应用程序加上图标。 任务栏图标: 软件左上角图标 可执行程序图标