天涯论坛网站建设,北京设计院排名100强,怎么还原wordpress,广州seo顾问服务牛客网 算法入门篇
判断一个链表是否为回文结构
给定一个单链表的头节点head#xff0c;请判断这个链表是否为回文结构1-2-1#xff0c;返回为True;1-2-3为False
思路#xff1a;
1#xff0c;遍历链表#xff0c;将所有元素压入栈中#xff0c;然后再…牛客网 算法入门篇
判断一个链表是否为回文结构
给定一个单链表的头节点head请判断这个链表是否为回文结构1-2-1返回为True;1-2-3为False
思路
1遍历链表将所有元素压入栈中然后再次从头遍历和栈中取出的元素比较。如果所有元素都是一致的化说明是属于回文结构的。2不是将所有的元素都入栈只是将一般的元素压入栈中引出新的问题如何确认链表的中点设计快指针和慢指针快指针每次移动2步慢指针每次移动1步当快指针移动到末尾慢指针所指向的位置就是链表的中点位置。但是链表长度需要分奇数和偶数。节约空间3不需要使用栈仅仅使用有限几个变量。和方法2一致使用快慢指针找到链表的中点将链表中点之后的元素逆序然后逐一比较但是需要注意的是最后需要将链表变回原先的样子。
代码
package class04;import java.util.Stack;public class Code04_IsPalindromeList {public static class Node {public int value;public Node next;public Node(int data) {this.value data;}}// need n extra spacepublic static boolean isPalindrome1(Node head) {StackNode stack new StackNode();Node cur head;while (cur ! null) {stack.push(cur);cur cur.next;}while (head ! null) {if (head.value ! stack.pop().value) {return false;}head head.next;}return true;}// need n/2 extra spacepublic static boolean isPalindrome2(Node head) {if (head null || head.next null) {return true;}Node right head.next;Node cur head;while (cur.next ! null cur.next.next ! null) {right right.next;cur cur.next.next;}StackNode stack new StackNode();while (right ! null) {stack.push(right);right right.next;}while (!stack.isEmpty()) {if (head.value ! stack.pop().value) {return false;}head head.next;}return true;}// need O(1) extra spacepublic 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 noden1 n1.next; // n1 - midn2 n2.next.next; // n2 - end}n2 n1.next; // n2 - right part first noden1.next null; // mid.next - nullNode n3 null;while (n2 ! null) { // right part convertn3 n2.next; // n3 - save next noden2.next n1; // next of right node convertn1 n2; // n1 moven2 n3; // n2 move}n3 n1; // n3 - save last noden2 head;// n2 - left first nodeboolean res true;while (n1 ! null n2 ! null) { // check palindromeif (n1.value ! n2.value) {res false;break;}n1 n1.next; // left to midn2 n2.next; // right to mid}n1 n3.next;n3.next null;while (n1 ! null) { // recover listn2 n1.next;n1.next n3;n3 n1;n1 n2;}return res;}public static void printLinkedList(Node node) {System.out.print(Linked List: );while (node ! null) {System.out.print(node.value );node node.next;}System.out.println();}public static void main(String[] args) {Node head null;printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);head.next new Node(2);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);head.next new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);head.next new Node(2);head.next.next new Node(3);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);head.next new Node(2);head.next.next new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);head.next new Node(2);head.next.next new Node(3);head.next.next.next new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);head.next new Node(2);head.next.next new Node(2);head.next.next.next new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();head new Node(1);head.next new Node(2);head.next.next new Node(3);head.next.next.next new Node(2);head.next.next.next.next new Node(1);printLinkedList(head);System.out.print(isPalindrome1(head) | );System.out.print(isPalindrome2(head) | );System.out.println(isPalindrome3(head) | );printLinkedList(head);System.out.println();}}将单链表按照给定的数值划分成左边小、中间相等、右边大的形式
思路
1申请一个链表长度大小一致的数组然后遍历链表的过程中将每一个点放到数组容器中在数组里面进行荷兰国旗问题再把数组容器中的元素都串联起来形成一个链表返回2保证稳定性根据题目要求设置三个区小于区、等于区和大于区每个区间包含两个变量开始节点和结尾节点一共设置6个变量6个变量都指向null当遇到第一个元素3的时候它是小于指定元素5的将小于区域的开始和结束指针都指向3第二个元素是5属于等于区让等于区的start和end都指向第二个元素5第3个元素也是5让等于区的end只想第三个元素。以此类推得到上面的结果。最后将小于区域的end指针链接等于区域的start指针等于区域的end指针链接大于区域的start指针。需要注意的是有可能上面6个变量有不存在的情形需要仔细判别。
两个单链表相交的一系列问题
给定两个可能有环也可能无环的单链表头节点head1和head2实现一个函数如果两个链表相交返回相交的第一个节点如果不相交返回null两个链表的长度之和为N时间复杂度为ON额外空间复杂度为O1相交共用内存地址 有环/无环写一个函数输入的类型是链表的头节点判断是否有环以及返回第一个有环的节点。使用集合来做遍历链表每遍历一个元素将其放入到集合中判定是否存在此元素如果将一个元素放入集合中发现他已经存在则是有环的并且他就是第一个入环节点。使用快慢指针来做快指针每次移动俩个位置慢指针每次移动一个位置当快慢指针第一次相交之后快指针回到链表的起始点慢指针呆在原地不动。然后快指针和慢指针都每次移动一个位置当他们再次相遇之后相遇的元素就是入环的第一个元素且能证明这个链表是有环的结构。上图所示的是环外4个点环内4个点可以按照这个流程走一遍。两个无环链表相交问题哪个链表长先走比短链表多余的部分然后一起走只要有一点的内存地址相稳合则代表两者相交。如果一个是有环的一个是无环的那么他俩一定不相交如果两者都是环状结构那么可以划分为上面三种形式。1两者都是环都不相交2两者共用环却已经在环外相交入环点一样3共用环但是接入环的点不一样。第一种情形如上图的左边的图形“6”loop1为相交点让loop1顺着next指针走一圈如果走了一圈没有遇到loop2则二者不相交。第二种类型只需要判断二者的入环节点是否一致就可以判定是否相交。如果需要判断相交的第一个节点入环点作为终止节点转化为先前的长短链找相交点。第一种情形如上图的右边的图形所示loop1为左边的相交点loop2为右边的相交点让loop1顺着next指针走一圈如果走了一圈遇到loop2则二者相交。loop1 和loop2都是相交节点只不过loop1距离链表1更近loop2距离链表2更近。
package class04;public class Code07_FindFirstIntersectNode {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;}// 找到链表第一个入环节点如果无环返回nullpublic static Node getLoopNode(Node head) {if (head null || head.next null || head.next.next null) {return null;}Node n1 head.next; // n1 - slowNode n2 head.next.next; // n2 - fastwhile (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 headwhile (n1 ! n2) {n1 n1.next;n2 n2.next;}return n1;}// 如果两个链表都无环返回第一个相交节点如果不想交返回nullpublic 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; // 谁长谁的头变成cur1cur2 cur1 head1 ? head2 : head1; // 谁短谁的头变成cur2n Math.abs(n);while (n ! 0) {n--;cur1 cur1.next;}while (cur1 ! cur2) {cur1 cur1.next;cur2 cur2.next;}return cur1;}// 两个有环链表返回第一个相交节点如果不想交返回nullpublic static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 null;Node cur2 null;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 {cur1 loop1.next;while (cur1 ! loop1) {if (cur1 loop2) {return loop1;}cur1 cur1.next;}return null;}}public static void main(String[] args) {// 1-2-3-4-5-6-7-nullNode head1 new Node(1);head1.next new Node(2);head1.next.next new Node(3);head1.next.next.next new Node(4);head1.next.next.next.next new Node(5);head1.next.next.next.next.next new Node(6);head1.next.next.next.next.next.next new Node(7);// 0-9-8-6-7-nullNode head2 new Node(0);head2.next new Node(9);head2.next.next new Node(8);head2.next.next.next head1.next.next.next.next.next; // 8-6System.out.println(getIntersectNode(head1, head2).value);// 1-2-3-4-5-6-7-4...head1 new Node(1);head1.next new Node(2);head1.next.next new Node(3);head1.next.next.next new Node(4);head1.next.next.next.next new Node(5);head1.next.next.next.next.next new Node(6);head1.next.next.next.next.next.next new Node(7);head1.next.next.next.next.next.next head1.next.next.next; // 7-4// 0-9-8-2...head2 new Node(0);head2.next new Node(9);head2.next.next new Node(8);head2.next.next.next head1.next; // 8-2System.out.println(getIntersectNode(head1, head2).value);// 0-9-8-6-4-5-6..head2 new Node(0);head2.next new Node(9);head2.next.next new Node(8);head2.next.next.next head1.next.next.next.next.next; // 8-6System.out.println(getIntersectNode(head1, head2).value);}}
