public static Node removeByRatio(Node head, int a, int b) { if (a < 1 || a > b) {` return head; } int n = 0; Node cur = head; while (cur != null) { n++; cur = cur.next; } n = (int) Math.ceil(((double) (a * n)) / (double) b); if (n == 1) { head = head.next; } if (n > 1) { cur = head; while (--n != 1) { cur = cur.next; } cur.next = cur.next.next; } return head; }
public static Node josephusKill1(Node head, int m) {
if (head == null || head.next == head || m < 1) {
return head;
}
Node last = head;
while (last.next != head) {
last = last.next;
}
int count = 0;
while (head != last) {
if (++count == m) {
last.next = head.next;
count = 0;
} else {
last = last.next;
}
head = last.next;
}
return head;
}
// need n extra space。空间复杂度为O(n/2)。利用栈
public static boolean isPalindrome1(Node head) {
Stack<Node> stack = new Stack<Node>();
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;
}
1
需要n/2的额外空间复杂度的代码：
// need n/2 extra space，额外空间复杂度为O(n/2)。这个方法是对第一种方法进行了改进，每次压右半部分的节点，这样从栈顶到栈底的顺序就相当于反过来了，然后与前半部分一一比较。
public 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;
}
Stack<Node> stack = new Stack<Node>();
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;
}
1
空间复杂度为仅仅为O(1)：
// need O(1) extra space
方法三：不需要栈和其他数据结构，只用有限几个变量，其额外空间复杂度为O(1)，可以在O(n)内完成所有的过程，也就是满足进阶的要求。具体过程如下：
1，首先改变链表右半部分的结构，使整个右半区反转，最后指向中间节点。
例如：1-->2-->3-->2-->1，通过这一步将其调整之后结构如下：1-->2-->3<--2<--1，链表1-->2-->3-->3-->2-->1，调整后为：1-->2-->3<--3<--2<--1。
我们把左半边区域第一个节点记为leftStart，把反转后的右半部分的最右边的节点记为rightStart。
2，leftStart和rightStart同时向中间点移动，移动每一步都比较leftStart和rightStart节点的值，看是否一样，一样的话，说明链表为为回文结构，否则不是回文结构。
3，不管最后返回时false还是true，在返回前都应该把链表恢复成原来的状况。
4，链表恢复成原来的样子，返回检查结果。以下是代码：
public 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 node，找到中间节点，和方法二有一点不一样，方法二的中间是从head.next开始，方法三是从head开始，这有什么区别呢？在节点为偶数的时候，方法二得到的中间是中间两个节点的后一个节点，而方法三得到的中间节点得到的是中间两个节点的前一个节点，为什么？因为方法二的情况下要压入节点进栈就是从后半部分开始，这样就可以理解了，实际上理解为后半部分更恰当。
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
n2 = n1.next; // n2 -> right part first node
n1.next = null; // mid.next -> null
Node n3 = null;
while (n2 != null) { // right part convert
n3 = n2.next; // n3 -> save next node
n2.next = n1; // next of right node convert
n1 = n2; // n1 move
n2 = n3; // n2 move
}
n3 = n1; // n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) { // check palindrome
if (n1.value != n2.value) {
res = false;
break;
}
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
n1 = n3.next;
n3.next = null;
while (n1 != null) { // recover list
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
```