• 算法拾遗十五补链表相关面试题

    算法拾遗十五补链表相关面试题

    判断链表是否相交

    给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的 第一个节点。如果不相交，返回null
    【要求】 如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度 请达到O(1)。
    思路：
    首先解决有环及无环的问题：如果无环返回空，如果有环返回第一个入环节点。
    下图框起来的则是第一个入环节点：
    在这里插入图片描述
    首先通过容器的办法解决这个问题，准备一个HashSet保留所有经过的节点，每经过一个节点都判断一下
    是否存在于HashSet里面。
    其次深入不用容器的方法（关键在于如何找到第一个入环节点）：准备一个快指针（一次走两步）以及一个慢指针（一次走一步），如果快指针提前走到空了，那么肯定是一个无环的单链表，那么快慢指针肯定会相遇，
    当相遇了之后将快指针移动到头节点，然后慢指针和快指针每次都走一步，相遇的位置就是第一个入环节点。
    在这里插入图片描述
    在上图点上S与F相遇了（S代表慢指针，F代表快指针）。
    接下来F回到开头，变成一次只走一步
    在这里插入图片描述
    S和F都走两步，相遇的点就是第一个入环节点。
    在这里插入图片描述
    同理如下边界条件也是成立的F回到头节点，而S则在那个环点上一直循环
    在这里插入图片描述
    代码如下：

    	// 找到链表第一个入环节点，如果无环，返回null
	public static Node getLoopNode(Node head) {
		//提前判断是否有三个点
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		// n1 慢  n2 快
		Node slow = head.next; // n1 -> slow
		Node fast = head.next.next; // n2 -> fast
		//如果快慢指针没有相遇则一直循环
		while (slow != fast) {
			if (fast.next == null || fast.next.next == null) {
				return null;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		// slow fast  相遇
		fast = head; // n2 -> walk again from head
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    接下来找到两个链表的第一个入环节点（loop1和loop2）
    1、如果都为空，则考虑两个无环的单链表该如何判断相交（类似于Y）
    如果有容器的话则用hashSet取出对应节点的内存地址
    Integer.toHexString(obj.hashCode())
    如果没有容器，从链表1出发找到第一个end1，找到长度len1
    从链表2出发找到end2，如果end1的内存地址和end2的内存地址不相等，则这个链表
    肯定不相交【end1和end2是相交的最后一个节点】
    那么如何求得相交得第一个节点呢？
    方式：
    如果链表1是100个节点，链表2是80个节点，先让链表1先迈20步，然后再让链表1和链表2
    一起走，则他们一定会在第一个相交得节点处相遇（因为end都是一样得只是长度不一样）
    代码如下：

    	// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
	public static Node noLoop(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0;
		//如果n为正数链表1长，负数链表2长
		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; // 谁长，谁的头变成cur1
		cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
		//cur1保存长链表的头，cur2保存短链表的头
		n = Math.abs(n);
		while (n != 0) {
			n--;
			//然后让长链表向后移动n步
			cur1 = cur1.next;
		}
		//长链表以及短链表一起走，直到相遇
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38

    2、分为一个链表有环和一个链表无环
    注：这种情况不可能相交（因为要相交肯定会造成两个链表成环的），如果一个链表不成环
    的话那么肯定不是相交的

    3、两个链表都有环（loop1和loop2都不为空）
    （1）两个环各自独立不相交
    在这里插入图片描述

    （2）统一理解为head1和head2入环节点是同一个在这里插入图片描述
    （3）这里入环节点不是同一个
    在这里插入图片描述
    这样就可以得出结论如果loop1等于loop2则是第二种情况，但是怎么求相交呢，则可以
    认为两个链表分别以loop1和loop2结尾，然后两个无环链表求交点。
    如果loop1不等于loop2，则要么是情况1要么是情况3，则从loop1开始走一圈看能否与
    loop2相遇，如果相遇了则是情况3，如果没有相遇则是情况1。
    代码如下：

    // 两个有环链表，返回第一个相交节点，如果不想交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		//情况2，跟之前的无环链表相交一样
		if (loop1 == loop2) {
			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 {
			//情况1或者情况3
			cur1 = loop1.next;
			//loop1开始往下循环找，如果在第一次循环的过程中找到loop2了，
			//那么则返回当前的交点，如果第一次循环结束了那么说明没有交点返回null
			while (cur1 != loop1) {
				if (cur1 == loop2) {
					return loop1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    整体代码如下：

    	public static class Node {
		public int value;
		public Node next;

		public Node(int data) {
			this.value = data;
		}
	}

	public static Node getIntersectNode(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node loop1 = getLoopNode(head1);
		Node loop2 = getLoopNode(head2);
		if (loop1 == null && loop2 == null) {
			return noLoop(head1, head2);
		}
		if (loop1 != null && loop2 != null) {
			return bothLoop(head1, loop1, head2, loop2);
		}
		return null;
	}

	// 找到链表第一个入环节点，如果无环，返回null
	public static Node getLoopNode(Node head) {
		//提前判断是否有三个点
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		// n1 慢  n2 快
		Node slow = head.next; // n1 -> slow
		Node fast = head.next.next; // n2 -> fast
		//如果快慢指针没有相遇则一直循环
		while (slow != fast) {
			if (fast.next == null || fast.next.next == null) {
				return null;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		// slow fast  相遇
		fast = head; // n2 -> walk again from head
		while (slow != fast) {
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

	// 如果两个链表都无环，返回第一个相交节点，如果不想交，返回null
	public static Node noLoop(Node head1, Node head2) {
		if (head1 == null || head2 == null) {
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0;
		//如果n为正数链表1长，负数链表2长
		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; // 谁长，谁的头变成cur1
		cur2 = cur1 == head1 ? head2 : head1; // 谁短，谁的头变成cur2
		//cur1保存长链表的头，cur2保存短链表的头
		n = Math.abs(n);
		while (n != 0) {
			n--;
			//然后让长链表向后移动n步
			cur1 = cur1.next;
		}
		//长链表以及短链表一起走，直到相遇
		while (cur1 != cur2) {
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

	// 两个有环链表，返回第一个相交节点，如果不想交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
		Node cur1 = null;
		Node cur2 = null;
		//情况2，跟之前的无环链表相交一样
		if (loop1 == loop2) {
			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 {
			//情况1或者情况3
			cur1 = loop1.next;
			//loop1开始往下循环找，如果在第一次循环的过程中找到loop2了，
			//那么则返回当前的交点，如果第一次循环结束了那么说明没有交点返回null
			while (cur1 != loop1) {
				if (cur1 == loop2) {
					return loop1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133

    总结

    能不能不给单链表的头节点，只给想要删除的节点，就能做到在链表上把这个点删掉?
    1、首先需要确定函数是需要返回一个node类型出去的，因为删除不排除要删掉头节点
    抖机灵的做法：给出要删除的结点，把该节点的next赋值给该节点，然后让该节点跨过下一个结点，让next指针指向下下一个节点其实这样本质上并没有把自己删除掉，除此之外，尾巴结点删除不掉
    如下整个链表为
    1->2->3->4->5->null
    我要删除3，我让自己变成4，然后变成 1 2 4 4 5
    然后再把后面的那个4给删除掉。
    这样就会导致最后的节点是删不掉的，
    如果要删除5，一方面是5的下面没东西，是个null，但是null是存在于系统的独立空间的。

  • 相关阅读:
    计算机408看不懂？那是你还不知道这套学习方法和资源
    说说Pluma插件管理框架
    SRC中逻辑漏洞检查总结
    Docker 镜像常用命令总结
    json-server环境搭建
    Spring——IOC 操作 Bean 管理（FactoryBean，作用域以及bean生命周期）
    web阶段javascript
    面试金典--面试题 17.21. 直方图的水量（不困难的困难题）
    VS2022新建项目时没有ASP.NET Web应用程序 （.NET Framework）
    神经网络在飞行疲劳检测中的应用综述
  • 原文地址：https://blog.csdn.net/lsdstone/article/details/126149935