西安网站建设云阔网络熊掌号,潘虎设计公司,菏泽网站建设优惠臻动传媒,西安观止软件科技有限公司链表中第一个公共节点
公节点定义#xff1a;同一个节点在两个链表中#xff0c;并不是节点值相同题目#xff1a;输入两个节点#xff0c;找出他们的第一个公共节点#xff0c;节点定义如需
/*** 链表元素节点** author liaojiamin* Date:Created in 12:17 2021/3/5*/
…链表中第一个公共节点
公节点定义同一个节点在两个链表中并不是节点值相同题目输入两个节点找出他们的第一个公共节点节点定义如需
/*** 链表元素节点** author liaojiamin* Date:Created in 12:17 2021/3/5*/
public class ListNode implements ComparableListNode {private String key;private Integer value;private ListNode next;private ListNode before;...本文中所有有关链表定义以及操作都使用自己实现的链表相关方法如需看详细实现可装到对应章节数据结构与算法–链表实现以及应用 两个单向链表特点在于只能同头开始遍历因此最简单方案还是双循环每次遍历链表A的节点时候与链表B中节点逐个比较直到找到相同的节点问题 这种方法实现简单但是时间复杂度是最大的如果A有m个阶段B有n个阶段那么时间复杂度是O(mn)应该有更好的方案 方案二 单向链表有共同节点因为每个节点都是有一个next指针因此从共同节点开始之后的所有节点都是相同的因此这个两个链表应该是个Y字形状如下图因为两个链表可能节点个数不同因此从头开始遍历不能直接得到那么如果从后开始遍历那边一定就是相同的节点如果能将链表反转从后向前遍历最后一个相同的节点就是我们需要求解的值如下图解 从后向前 如上图第一个想到的方法是反转链表因为单向链表只能从头开始反转后可以从尾部开始遍历反转后出现如下情况 当修改第一个链表时候第二个链表其实也被修改了并且此时已经找不到地儿个链表的尾部节点因此方法是不成了。还有另外方法我们将链表的每个节点存储到另外一个数组中然后从数组尾部开始遍历那么用栈来存储链表节点此时是最适合的遍历两个链表分别存储两个栈stack1 stack2,接着遍历stack1 stack2 因为后进先出因此先处理的必然是相等的我们只需要找到第一个不相等的节点如下实现此处对栈的定义以及相关方法的实现都是用的自己对栈的实现方法可到之前对应章节查看详细的实现数据结构与算法–简单栈实现及其应用
/*** 寻找两个单向链表的第一个公共节点* 公共节点定义同一个节点在两个链表中并不是节点值相同** author liaojiamin* Date:Created in 15:30 2021/6/15*/
public class FindFirstCommonNode {public static void main(String[] args) {Random random new Random();Integer number1 random.nextInt(100);ListNode node1 new ListNode(number1.toString(), number1);for (int i 0; i 3; i) {Integer number random.nextInt(100);ListNode newNode new ListNode(number.toString(), number);MyLinkedList.addToTail(node1, newNode);}Integer number2 random.nextInt(100);ListNode node2 new ListNode(number2.toString(), number2);for (int i 0; i 6; i) {Integer number random.nextInt(100);ListNode newNode new ListNode(number.toString(), number);MyLinkedList.addToTail(node2, newNode);}ListNode node3 new ListNode(x, 3);MyLinkedList.addToTail(node1, node3);MyLinkedList.addToTail(node2, node3);for (int i 0; i 3; i) {Integer number random.nextInt(100);ListNode newNode new ListNode(number.toString(), number);MyLinkedList.addToTail(node1, newNode);}MyLinkedList.print(node1);System.out.println();MyLinkedList.print(node2);ListNode commonNode findFirstCommonNodeStack(node1, node2);System.out.println();System.out.println(commonNode.getKey());}/*** 方法一栈方法后进先出*/public static ListNode findFirstCommonNodeStack(ListNode node1, ListNode node2) {if (node1 null || node2 null) {return null;}if (node1.getNext() null node2.getNext() null) {return node1.equals(node2) ? node1 : null;}MyStack stack1 new MyStack();ListNode head node1;while (head ! null) {stack1.push(head);head head.getNext();}MyStack stack2 new MyStack();head node2;while (head ! null) {stack2.push(head);head head.getNext();}ListNode commonNode null;while (!stack1.isEmpty() !stack2.isEmpty()) {ListNode popStack1 (ListNode) stack1.pop();ListNode popStack2 (ListNode) stack2.pop();if (popStack1.equals(popStack2)) {commonNode popStack1;}}return commonNode;}
}利用栈额外存储了一份节点数据来找到对应的相同节点用空间换时间的方法时间复杂度O(mn)空间复杂度O(mn) 方法三 如果题目有更苛刻的要求不能使用额外空间在这种情况下我先想到的是双指针法我们在之前的文章数据结构与算法–代码鲁棒性案例分析中详细介绍了双指针法获取链表中倒数第N个数此处有两个链表自然想到双指针。但是分析发现此时两个链表可能元素个数不同双指针同样也需要O(mn)的时间复杂度还是受到数据结构与算法–代码鲁棒性案例分析 中双指针的启发其中A指针先走了n步骤B指针才开始遍历当A指针到尾部B指针就是倒数第n个数据此处同样的思想我们先查询AB链表长度如果A比B长N 那么让A指针先走N不那么AB指针则在统一起跑线。此时同时遍历AB并且比较对应节点直到找到相同的第一个节点为止经如上分析有如下代码
/*** 寻找两个单向链表的第一个公共节点* 公共节点定义同一个节点在两个链表中并不是节点值相同** author liaojiamin* Date:Created in 15:30 2021/6/15*/
public class FindFirstCommonNode {public static void main(String[] args) {Random random new Random();Integer number1 random.nextInt(100);ListNode node1 new ListNode(number1.toString(), number1);for (int i 0; i 3; i) {Integer number random.nextInt(100);ListNode newNode new ListNode(number.toString(), number);MyLinkedList.addToTail(node1, newNode);}Integer number2 random.nextInt(100);ListNode node2 new ListNode(number2.toString(), number2);for (int i 0; i 6; i) {Integer number random.nextInt(100);ListNode newNode new ListNode(number.toString(), number);MyLinkedList.addToTail(node2, newNode);}ListNode node3 new ListNode(x, 3);MyLinkedList.addToTail(node1, node3);MyLinkedList.addToTail(node2, node3);for (int i 0; i 3; i) {Integer number random.nextInt(100);ListNode newNode new ListNode(number.toString(), number);MyLinkedList.addToTail(node1, newNode);}MyLinkedList.print(node1);System.out.println();MyLinkedList.print(node2);System.out.println();ListNode commonNode2 findFirstCommonNode(node1, node2);System.out.println(commonNode2.getKey());}/*** 方法二错位遍历* */public static ListNode findFirstCommonNode(ListNode node1, ListNode node2){if (node1 null || node2 null) {return null;}if (node1.getNext() null node2.getNext() null) {return node1.equals(node2) ? node1 : null;}Integer countNode1 0;ListNode header node1;while (header ! null){countNode1 ;header header.getNext();}Integer countNode2 0;header node2;while (header ! null){countNode2 ;header header.getNext();}Integer prefix Math.abs(countNode1 - countNode2);ListNode header1 node1;ListNode header2 node2;if(countNode1 countNode2){for (int i 0; i prefix; i){if(header1 ! null){header1 header1.getNext();}}}else {for (int i 0; i prefix; i){if(header2 ! null){header2 header2.getNext();}}}while (header1 ! null header2 ! null){if(header1.equals(header2)){return header1;}header1 header1.getNext();header2 header2.getNext();}return null;}
}方法三中没有用到额外的存储空间时间复杂度同样也是O(mn)要优于方法二这是目前想到的最优方案。
上一篇数据结构与算法–数组中的逆序对 下一篇数据结构与算法–最小的k个数
