上海opencart网站建设,电子网络工程建设范围,东莞保安公司排名前十,劳务派遣好还是外包好这里写目录标题 公共子节点采用集合或者哈希采用栈拼接两个字符串差和双指针 旋转链表 公共子节点
例如这样一道题#xff1a;给定两个链表#xff0c;找出它们的第一个公共节点。 具体的题目描述我们来看看牛客的一道题#xff1a; 这里我们有四种解决办法#xff1a; … 这里写目录标题 公共子节点采用集合或者哈希采用栈拼接两个字符串差和双指针 旋转链表 公共子节点
例如这样一道题给定两个链表找出它们的第一个公共节点。 具体的题目描述我们来看看牛客的一道题 这里我们有四种解决办法
采用集合或者哈希
思路是这样的我们先把其中一个链表遍历放入Map中然后遍历第二个第二个链表与Map中的对比第一个相同的即为公共节点。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {MapListNode, Integer map new HashMap();while (pHead1 ! null) {map.put(pHead1, pHead1.val);pHead1 pHead1.next;}while (pHead2 ! null) {if (map.containsKey(pHead2)) {return pHead2;}pHead2 pHead2.next;}return null;}采用栈
这种方法我们需要两个栈把两个链表分别遍历入栈然后同时弹出相同且最晚出栈的那一组即为公共节点。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {StackListNode stack1 new Stack();StackListNode stack2 new Stack();while (pHead1 ! null) {stack1.push(pHead1);pHead1 pHead1.next;}while (pHead2 ! null) {stack2.push(pHead2);pHead2 pHead2.next;}ListNode ret null;while (stack1.size() 0 stack2.size() 0) {if (stack1.peek() stack2.peek()) {ret stack1.pop();stack2.pop();} else {break;}}return ret;}拼接两个字符串
先看下面的两个链表 A1-4-6-2-3-5 B2-3-5 我们试着拼接一个 AB1-4-6-2-3-5-2-3-5 BA2-3-5-1-4-6-2-3-5 我们会发现链表只要有公共的节点那么我们遍历AB与BA就会找到公共节点。 public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {if (pHead1 null || pHead2 null) {return null;}ListNode p1 pHead1;ListNode p2 pHead2;while (p1 ! p2) {p1 p1.next;p2 p2.next;//防止陷入死循环if (p1 ! p2) {if (p1 null) {p1 pHead2;}if (p2 null) {p2 pHead1;}}}return p1;}差和双指针
遍历两个链表记录两个链表的长度然后先遍历较长链表len1-len2绝对值个节点然后两个链表同时向前走节点一样的时候就是公共节点。
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {if (pHead1 null || pHead2 null) {return null;}ListNode p1 pHead1;ListNode p2 pHead2;int len1 0, len2 0;while (p1 ! null) {p1 p1.next;len1;}while (p2 ! null) {p2 p2.next;len2;}int sub Math.abs(len1 - len2);ListNode current1 pHead1;ListNode current2 pHead2;if (len1 len2) {int a 0;while (a sub) {current1 current1.next;a;}}if (len2 len1) {int a 0;while (a sub) {current2 current2.next;a;}}while (current1 ! current2) {current1 current1.next;current2 current2.next;}return current2;}这段代码是一个Java方法用于查找两个链表中的第一个公共节点。方法名为FindFirstCommonNode,接收两个参数pHead1和pHead2,分别表示两个链表的头节点。 首先判断两个链表是否为空如果有一个为空则返回null。 然后使用两个指针p1和p2分别遍历两个链表计算它们的长度len1和len2。 接下来计算两个链表长度之差的绝对值sub。 再接着创建两个新的指针current1和current2,分别指向两个链表的头节点。如果链表1的长度大于链表2的长度将current1向后移动sub个节点如果链表2的长度大于链表1的长度将current2向后移动sub个节点。 最后同时遍历两个链表直到找到第一个相同的节点将其返回。
旋转链表
我们有两种思路 将前k部分与N-k部分分别反转连接起来就解决了。用双指针找到倒数K的位置具体实现如下 public ListNode rotateRight(ListNode head, int k) {if(headnull || k0){return head;}ListNode fast head;ListNode slow head;ListNode temp head;int len 0;while (head!null){head head.next;len;}if(k%len0){return temp;}while (k%len0){k--;fast fast.next;}while (fast.next!null){fast fast.next;slow slow.next;}ListNode res slow.next;fast.next temp;slow.nextnull;
return res;}首先判断链表是否为空或旋转位置数是否为0,如果满足任一条件则直接返回原链表头节点。初始化三个指针fast、slow和temp,都指向链表头节点。同时定义一个变量len用于记录链表的长度。遍历链表计算链表的长度。判断旋转位置数k是否能被链表长度整除如果能整除则不需要旋转直接返回原链表头节点。如果旋转位置数k不能被链表长度整除需要找到k对链表长度取模后的余数对应的节点位置。通过fast指针先向前移动k%len个位置然后fast和slow指针同时向前移动直到fast指针到达链表尾部。此时slow指针所在的位置就是需要旋转后的新头节点。将新头节点的下一个节点作为新链表的尾节点将原链表的尾节点接到新链表的头部形成新的链表。返回新的链表头节点。
