Skip to content

Commit dba12af

Browse files
mood321mood321
committed
算法 题
1 parent f5e353d commit dba12af

2 files changed

Lines changed: 253 additions & 1 deletion

File tree

‎src/main/java/algorithm/basic03/Code_11_IsPalindromeList.java‎

Lines changed: 226 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,226 @@
1+
package algorithm.basic03;
2+
3+
import java.util.Stack;
4+
5+
/**
6+
* @Created by mood321
7+
* @Date 2019/10/28 0028
8+
* @Description TODO
9+
*/
10+
public class Code_11_IsPalindromeList {
11+
public static class Node {
12+
int data;
13+
Node next;
14+
15+
Node(int data) {
16+
this.data = data;
17+
}
18+
}
19+
20+
// need n extra space
21+
public static boolean isPalindrome1(Node head) {
22+
if (head == null || head.next ==null){
23+
return false;
24+
}
25+
Stack<Node> stack = new Stack<>();
26+
Node cur = head;
27+
while (cur != null) {
28+
stack.push(cur);
29+
cur = cur.next;
30+
}
31+
while (head != null) {
32+
if (head.data != stack.pop().data) {
33+
return false;
34+
}
35+
head = head.next;
36+
}
37+
return true;
38+
}
39+
40+
// need n/2 extra space
41+
public static boolean isPalindrome2(Node head) {
42+
if (head == null || head.next ==null){
43+
return false;
44+
}
45+
Node left = head;
46+
Node right = head;
47+
while (right.next != null && right.next.next != null) {
48+
left = left.next;
49+
right = right.next.next;
50+
}
51+
Stack<Node> stack = new Stack<>();
52+
while (left != null) {
53+
stack.push(left);
54+
left = left.next;
55+
}
56+
while (!stack.isEmpty()) {
57+
if (stack.pop().data != head.data) {
58+
return false;
59+
60+
}
61+
head = head.next;
62+
}
63+
return true;
64+
}
65+
66+
// need O(1) extra space
67+
public static boolean isPalindrome3(Node head) {
68+
if (head == null || head.next == null) {
69+
return true;
70+
}
71+
Node left = head;
72+
Node right = head;
73+
while (right.next != null && right.next.next != null) { // find mid node
74+
left = left.next; // left -> mid
75+
right = right.next.next; // right -> end
76+
}
77+
right = left.next; // right -> right part first node
78+
left.next = null; // mid.next -> null
79+
Node tem = null;
80+
while (right != null) { // right part convert
81+
tem = right.next; // tem -> save next node
82+
right.next = left; // next of right node convert
83+
left = right; // left move
84+
right = tem; // right move
85+
}
86+
tem = left; // tem -> save last node
87+
right = head;// right -> left first node
88+
boolean res = true;
89+
while (left != null && right != null) { // check palindrome
90+
if (left.data != right.data) {
91+
res = false;
92+
break;
93+
}
94+
left = left.next; // left to mid
95+
right = right.next; // right to mid
96+
}
97+
left = tem.next;
98+
tem.next = null;
99+
while (left != null) { // recover list
100+
right = left.next;
101+
left.next = tem;
102+
tem = left;
103+
left = right;
104+
}
105+
return res;
106+
}
107+
108+
private static Node reverse(Node left1,Node stop) {
109+
Node left=left1;
110+
Node right = left.next;
111+
left.next = null;
112+
Node tem = null;
113+
while (right != null) {
114+
if(left==stop){
115+
break;
116+
}
117+
tem = right.next;
118+
right.next = left;
119+
left = right;
120+
right = tem;
121+
}
122+
return left;
123+
}
124+
125+
126+
public static void printLinkedList(Node node) {
127+
System.out.print("Linked List: ");
128+
while (node != null) {
129+
System.out.print(node.data + " ");
130+
node = node.next;
131+
}
132+
System.out.println();
133+
}
134+
135+
public static void main(String[] args) {
136+
137+
Node head = null;
138+
/* printLinkedList(head);
139+
System.out.print(isPalindrome1(head) + " | ");
140+
System.out.print(isPalindrome2(head) + " | ");
141+
System.out.println(isPalindrome3(head) + " | ");
142+
printLinkedList(head);
143+
System.out.println("=========================");
144+
145+
head = new Node(1);
146+
printLinkedList(head);
147+
System.out.print(isPalindrome1(head) + " | ");
148+
System.out.print(isPalindrome2(head) + " | ");
149+
System.out.println(isPalindrome3(head) + " | ");
150+
printLinkedList(head);
151+
System.out.println("=========================");
152+
153+
head = new Node(1);
154+
head.next = new Node(2);
155+
printLinkedList(head);
156+
System.out.print(isPalindrome1(head) + " | ");
157+
System.out.print(isPalindrome2(head) + " | ");
158+
System.out.println(isPalindrome3(head) + " | ");
159+
printLinkedList(head);
160+
System.out.println("=========================");
161+
162+
head = new Node(1);
163+
head.next = new Node(1);
164+
printLinkedList(head);
165+
System.out.print(isPalindrome1(head) + " | ");
166+
System.out.print(isPalindrome2(head) + " | ");
167+
System.out.println(isPalindrome3(head) + " | ");
168+
printLinkedList(head);
169+
System.out.println("=========================");
170+
171+
head = new Node(1);
172+
head.next = new Node(2);
173+
head.next.next = new Node(3);
174+
printLinkedList(head);
175+
System.out.print(isPalindrome1(head) + " | ");
176+
System.out.print(isPalindrome2(head) + " | ");
177+
System.out.println(isPalindrome3(head) + " | ");
178+
printLinkedList(head);
179+
System.out.println("=========================");
180+
181+
head = new Node(1);
182+
head.next = new Node(2);
183+
head.next.next = new Node(1);
184+
printLinkedList(head);
185+
System.out.print(isPalindrome1(head) + " | ");
186+
System.out.print(isPalindrome2(head) + " | ");
187+
System.out.println(isPalindrome3(head) + " | ");
188+
printLinkedList(head);
189+
System.out.println("=========================");
190+
191+
head = new Node(1);
192+
head.next = new Node(2);
193+
head.next.next = new Node(3);
194+
head.next.next.next = new Node(1);
195+
printLinkedList(head);
196+
System.out.print(isPalindrome1(head) + " | ");
197+
System.out.print(isPalindrome2(head) + " | ");
198+
System.out.println(isPalindrome3(head) + " | ");
199+
printLinkedList(head);
200+
System.out.println("=========================");
201+
202+
head = new Node(1);
203+
head.next = new Node(2);
204+
head.next.next = new Node(2);
205+
head.next.next.next = new Node(1);
206+
printLinkedList(head);
207+
System.out.print(isPalindrome1(head) + " | ");
208+
System.out.print(isPalindrome2(head) + " | ");
209+
System.out.println(isPalindrome3(head) + " | ");
210+
printLinkedList(head);
211+
System.out.println("=========================");
212+
*/
213+
head = new Node(1);
214+
head.next = new Node(2);
215+
head.next.next = new Node(3);
216+
head.next.next.next = new Node(2);
217+
head.next.next.next.next = new Node(1);
218+
printLinkedList(head);
219+
System.out.print(isPalindrome1(head) + " | ");
220+
System.out.print(isPalindrome2(head) + " | ");
221+
System.out.println(isPalindrome3(head) + " | ");
222+
printLinkedList(head);
223+
System.out.println("=========================");
224+
225+
}
226+
}

‎src/main/resources/note/Algorithm/算法学习笔记.md‎

Lines changed: 27 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -193,4 +193,30 @@
193193
<p>【题目】 给定两个有序链表的头指针head1和head2，打印两个链表的公共部分。
194194
<p> 思路: 有序链表 可以用归并排序 合并两集合的思路-- 比较 相同下移
195195
<p> <a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic03/Code_10_PrintCommonPart.java"> code</a>
196-
196+
197+
+ 判断一个链表是否为回文结构
198+
<p>【题目】 给定一个链表的头节点head，请判断该链表是否为回文结构。 例如： 1->2->1，返回true。 1->2->2->1，返回true。
199+
<p>15->6->15，返回true。 1->2->3，返回false。
200+
<p>进阶： 如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)
201+
<p> 思路: 1 用栈 首次压栈 出栈和原链表应该一直O(n)
202+
<p> 2 双指针 一个指针一次走一步 一个指针一次走两步 走的快的指针走到tail 另一指针必在中点 压栈 和头结点比较(时间复杂度 是 前一个的一半)
203+
<p> 3 双指针 还是一个指针走到尾部 反转后半部分链表 比较true/flase 还原 实现去掉辅助空间
204+
<p> <a href="https://github.com/mood321/JavaDemo/blob/master/src/main/java/algorithm/basic03/Code_10_PrintCommonPart.java"> code</a>
205+
206+
207+
+ 将单向链表按某值划分成左边小、中间相等、右边大的形式
208+
【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个
209+
整 数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot
210+
的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。
211+
除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5-
212+
>1，pivot=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总
213+
之，满 足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部
214+
分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做 要求。
215+
进阶： 在原问题的要求之上再增加如下两个要求。
216+
在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左 到右的
217+
顺序与原链表中节点的先后次序一致。 例如：链表9->0->4->5->1，pivot=3。
218+
调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到
219+
右为0、1。在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再
220+
讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4，
221+
最后出现5。
222+
如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)

0 commit comments

Comments
 (0)