Java算法基础4Hash/有序表/链表

老$¥

2024-04-25 帮助1人

学新通
注意：Hash表在使用的时候认为时间复杂度都是常熟级别，数据量再大也是常数时间返回值，只是比较大。

HashMap，带key和value，以key来组织
学新通
如上图，put方法既是新增，也是更新value，首先让加了一条记录叫1zuo,第二条更新，将1所对应的value改为cheng

String类型直接把内存地址一个拷贝放到hash（一律只占八位），内存地址作为key。

如下图，可以remove一个key，会连同这个key对应的value一起删掉
学新通
get用来查询某一个key存在跟不存在，也可以把key对应的value拿出来，这就是从查。

学新通

如下图，string类型的key对应string类型的value
hash表怎么占用空间？==> key的值，就是下图第一个"aadfkasfkjasd"，一律拷贝一份放到hash表里。hash表内部按值传递。所以这里可以直接用node来指向value。hash不会把它拷贝一份，而是会把它的地址拷贝一份作为我的记录
。参考下下图。node A和 node B不一样，因为内部地址不一样。
学新通

学新通

学新通
hash表是无序组织key，有序表是有序组织key

所以hash能实现的有序表都能实现，并且还能根据key有序这件事延伸出新功能。

学新通
有序表操作级别是O(logN）级别

学新通

链表

学新通

链表基础知识
 链表刷题
 双向链表

学新通

反转单向链表（栈）

学新通

//传入参数是头结点，返回参数也要是新链表头结点

public class ListNode
{
	int val;
	ListNode next = null;

	ListNOde(int val){
	this.val = val;
}

import java.util.Stack;
public class Soultion
{
	public ListNode ReverseList(ListNode head)
	{
		Stack<ListNode> stack = new Stack<>();
	//将旧链表从头开始依次入栈
		while(head != NULL)
		{
			stack.push(head);
			head = head.next;
		}

	if(stack.isEmpty()) return null;//如果栈是空，证明链表是空链表

	ListNode node = stack.pop();//新链表第一个节点
	ListNode result = node;//最后的返回值，新链表的头结点

	while(!stack.isEmpty())
	{
		ListNode tempNode = stack.pop();
		node.next = tempNode;
		node = node.next;
	}

	node.next = null;//最后一个节点指针指null，不然会成环

	return result;
	}
}
}

双链表反转

双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表。下面以链表1→2→3→4为例画个图来看下。

学新通

他每次访问的原链表节点都会成为新链表的头结点，最后再来看下代码

public ListNode ReverseList(ListNode head) {
    //新链表
    ListNode newHead = null;
    while (head != null) {
        //先保存访问的节点的下一个节点，保存起来
        //留着下一步访问的
        ListNode temp = head.next;
        //每次访问的原链表节点都会成为新链表的头结点，
        //其实就是把新链表挂到访问的原链表节点的
        //后面就行了
        head.next = newHead;
        //更新新链表
        newHead = head;
        //重新赋值，继续访问
        head = temp;
    }
    //返回新链表
    return newHead;
}

注意：链表的调整可能会存在换头的操作，那就带返回值，不换头可以定义成void类型。

学新通
这道题其实类似于下图，外排序，用两个指针指着两个链表第一个如下图，谁小谁向右移动，相等时将value放入新数组，然后一起移动。有一个越界了就停。

学新通

学新通
打印完成后共同移动

学新通

笔试：直接放到栈里就行

栈先进后出，放进去以后弹出来就是倒着的，比较和原来链表一不一样就行。额外空间O(n)

更省空间的做法：把链表右边部分放入栈，然后弹出跟原链表从头开始比。
这种方法就用快慢指针（重要技巧）找到中点才行。额外空间O(n/2)

快慢指针：快指针一次走两步，慢指针一次走一步。快指针走完的时候，慢指针来到中点的位置。这个时候就可以把慢指针后面的东西放到栈里面去了。

如下图，快慢指针一定要自己code，根据长度是奇数还是偶数分析它。进行微调。比如长度为偶数，在快指针走完时需要慢指针指向中间的前一个数还是后一个数。

一定要写熟练！！！
学新通
如果只用有限几个变量如何解决这个问题？这种方法额外空间复杂度只需要O(1)

然后中点往下遍历的时候将其逆序，中点指向空，剩下的往回指，如下图，A和B同时往中间走，每一步去比对，有一个走到空就停下来。最后完了把右边部分链表恢复正常，然后返回true/false。

学新通
然后返回true/false之前，将链表恢复如下图。

笔试直接将其放到Node类型数组里面，然后partition（荷兰国旗问题），最后把它们串起来就可以了。

面试就不要用数据结构，要用有限几个变量搞定它。

下图以5做划分值，只改变几个有限变量实现荷兰国旗问题，还要实现相对顺序不变。

学新通

用6个变量就够了。
SH：小于部分的头
ST：小于部分的尾
EH：等于部分的头
ET：等于部分的尾
bH: 大于部分的头
bT：大于部分的尾
学新通
4节点，第一个发现小于5的节点，SH和ST（头尾）都指向4

然后6节点调整bH,bT

3节点，也是小于5的，让之前发现小于5的next指针指向3，然后让3变成此时的尾巴。内部next指针是串好的，头指针指向4，尾指针指向3.
学新通

继续

学新通

最后小于区域的尾连接等于区域的头，等于区域的尾连接大于区域的头。一定要讨论清楚边界，不然可能用到空指针报错。

学新通

//荷兰国旗解法
public static void arrPartition(Node[] nodeArr, int pivot) {
		int small = -1;
		int big = nodeArr.length;
		int index = 0;
		while (index != big) {
			if (nodeArr[index].value < pivot) {
				swap(nodeArr,   small, index  );
			} else if (nodeArr[index].value == pivot) {
				index  ;
			} else {
				swap(nodeArr, --big, index);
			}
		}
	}

//六个变量解法

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;
	}

学新通
如下图，要完全copy一个链表，value一样，指向指针一样，rand指针也要一样。

如果用额外空间直接hash表解决

//用额外空间，哈希表解决

准备一张哈希表，map
key是Node类型，表示老节点，value也是Node类型，表示老节点对应的克隆出来的新节点

不用考虑新链表怎么连，就把每一个老链表拷贝出来新链表，然后放到这个map里去，

第二步开始设置新链表next和random方向的指针，遍历哈希表或者遍历老链表来设置指针

遍历到1，其克隆节点1’，其next就是2’（因为1next为2），random同理设置成3‘。最后返回1’

学新通

public static Node copyListWithRand1(Node head) {
		HashMap<Node, Node> map = new HashMap<Node, Node>();/
		/hash，Node里面存的是内存地址
		Node cur = head;
		//第一个while把map生成克隆节点
		while (cur != null) {
			map.put(cur, new Node(cur.value));
			//来到当前cur，做出其克隆节点，然后挂到map里去
			cur = cur.next;//每个节点都这么干
		}
		//第一个while，对应关系记好了，克隆节点生成了。
		
		cur = head;//cur从头出发
		//再遍历一遍老链表
		while (cur != null) {
		//map.get(cur) = =cur'，即克隆节点，get找到cur'
		//参考下图，cur.next就是?  map对应?'   cur'指向?'
			map.get(cur).next = map.get(cur.next);//右边结果是?'
			//下面是random指针
			map.get(cur).rand = map.get(cur.rand);
			cur = cur.next;
		}
		//返回老头部所对应的克隆节点，就是新头部的头
		return map.get(head);
	}

学新通

链表有环问题

学新通
三种情况

有环无环相交（不可能情况）
无环无环相交
有环有环相交
相交就是共用节点的意思，如下图，被方框框起来的节点是第一个相交节点。这道题本身和节点value无关，而是看是否有某个节点内存地址一样。

学新通
怎么判断单独链表，有环无环？有环的话返回第一个入环节点，如下图，红圈是第一个入环节点

学新通

最简单的方法就是hash，参考下图。HashSet，每一个节点看在不在集合里，不在就放进hashset，第二次到c发现在集合里，c就是第一个入环节点。

学新通

不用数据结构方法判断，较难，原理是快慢指针。

//不用额外数据结构，用快慢指针，很难

学新通

PS：如果一个单链表有环，一定会掉到自己的环里出不来，因为只有一个next指针
下图为快慢指针，

记住结论解题流程：一开始快慢指针都停留在开始节点处，慢指针每次走一步，快指针每次走两步，它们一定会在环上相遇。相遇的时候快指针回到开头变成一次走一步，慢指针停在原地，继续一次走一步。再次相遇的时刻一定在第一个入环的节点处。

如果走到头说明无环。
如果没走到头，快慢指针第一次相遇后（一定在环上相遇），快指针也变成一次走一步且跳到开头，二者再次相遇一定在环入口。**

学新通

两个无环单链表，如果有一个节点相交，此节点开始往后部分都是共有部分，如下图。根据这个结论，下下图，比较这两个链表的最后一个节点地址是否相等（end1是否等于end2），不相等肯定不相交。相等的话，开始寻找第一个相交节点。

比如链表1长度为100，链表2长度为80，先让链表1走20步，然后链表1,2一起向前，比较节点，一定会到第一个共同相交的节点上。
学新通

学新通
相交与不相交，两种情况

学新通

public static Node noLoop(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0;
		while (cur1.next != null) {
			n  ;
			cur1 = cur1.next;
		}
		while (cur2.next != null) {
			n--;
			cur2 = cur2.next;
		}
		if (cur1 != cur2) {
			return null;
		}
		//n是链表1减链表2的长度，
		cur1 = n > 0 ? head1 : head2;//谁长，谁的头变成curl1
		cur2 = cur1 == head1 ? head2 : head1;//谁短，谁的头变成curl2
		n = Math.abs(n);
		while (n != 0) {
			n--;
			cur1 = cur1.next;
		}
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

PS：一个链表有环，一个链表无环，不可能相交

学新通

两个链表都有环，有下图三种情况

学新通
针对这种情况，怎么求第一个相交的节点。

已知条件：head1第一个入环节点叫loop1，head2第一个入环接节点叫loop2，
情况2最好区分，loop1的地址等于loop2的地址==>这种情况怎么求第一个相交的节点？==>这就是无环链表的相交问题（就假设，认为入环的那个节点是终止位置就行，直接复用无环链表code就行）。

情况1和情况3怎么区分？==>让loop1继续往下走，在转回自己的过程中能遇到loop2就是第三种情况，遇不到loop2就是第一种情况。

学新通

这篇好文章是转载于：学新通技术网

Java算法基础4Hash/有序表/链表

链表

反转单向链表（栈）

双链表反转

链表有环问题

photoshop保存的图片太大微信发不了怎么办

《学习通》视频自动暂停处理方法

Android 11 保存文件到外部存储，并分享文件

word里面弄一个表格后上面的标题会跑到下面怎么办

photoshop扩展功能面板显示灰色怎么办

微信公众号没有声音提示怎么办

excel下划线不显示怎么办

excel打印预览压线压字怎么办

怎样阻止微信小程序自动打开

TikTok加速器哪个好免费的TK加速器推荐