k 反转链表
k reverse a linked list
这里,我想递归地反转链表的每k个元素。对于链表
3 → 4 → 5 → 2 → 6 → 1 → 9
对于 kReverse(3)
变为 5 → 4→ 3→ 1→ 6→ 2→ 9→ 1
我收到 NullPointerException
.
public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k, int size) {
if(size<k) {
return ReverseLinkedList.reverseLinkedList(head);
}
Node<Integer> temp = head;
int i=1;
while(i<k) {
temp = temp.next;
i++;
}
Node<Integer> newHead = temp;
temp.next=null;
ReverseLinkedList.reverseLinkedList(head);
Node<Integer> smallerHead = kReverseLinkedList(head.next, k, size-k);
head.next = smallerHead;
return newHead;
}
粗略地看一下,您没有更新递归来使用 newHead。
此外,你需要注意打破和制造指针。当您保留前 3 个元素时,它们需要指向它们的前一个。
4.next = 3 和 5.next = 4(您需要在代码中进行管理)
一个提示:
使用大小为 k 的 堆栈会容易得多,它会递归地反转所需的元素并在其满时弹出。
我不确定这是不是你想要的?
不需要尺寸,
public class Node<T> {
private T item;
private Node<T> next;
public Node(T item, Node<T> next) {
this.item = item;
this.next = next;
}
public Node(T item) {
this.item = item;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
public static Node<Integer> reverseLinkedList(Node<Integer> head) {
if (head.next != null){
Node<Integer> prev = head.next;
Node<Integer> result = reverseLinkedList(prev);
prev.next = head;
return result;
} else {
return head;
}
}
private static Node<Integer> kReverseLinkedList(Node<Integer> head, Node<Integer> cursor, int counter, int k) {
Node<Integer> result;
if (cursor.next == null){
result = reverseLinkedList(head);
head.next = null;
} else if (counter > 0){
result = kReverseLinkedList(head, cursor.next, counter-1, k);
} else {
Node<Integer> next = cursor.next;
cursor.next = null;
result = reverseLinkedList(head);
head.next = kReverseLinkedList(next, next, k, k);
}
return result;
}
public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k) {
Node<Integer> result = null;
if (head != null){
result = head;
if (k > 1) {
result = kReverseLinkedList(head, head, k-1, k-1);
}
}
return result;
}
public static void print(Node<Integer> n) {
if (n != null){
System.out.print(n.item+" ");
print(n.next);
} else {
System.out.println();
}
}
public static void main(String[] args) {
int[] data = {3,4,5,2,6,1,9};
Node<Integer> head = new Node<>(data[0]);
Node<Integer> tail = head;
for (int i = 1; i < data.length; i++) {
Node<Integer> n = new Node<>(data[i]);
tail.setNext(n);
tail = n;
}
print(head);
head = kReverseLinkedList(head, 3);
print(head);
}
}
输出:
3 4 5 2 6 1 9
5 4 3 1 6 2 9
我认为递归版本中不需要循环。
要使其通用,请添加一个偏移量。
不需要尺寸。
这里是带偏移量的真实递归版本(未测试):
private static Node<Integer> tail;
public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k, int offset, Node<Integer> current) {
if (offset > 1) {
kReverseLinkedList(head.next, k, offset - 1, head.next);
return head;
} else if (offset == 1) {
head.next = kReverseLinkedList(head.next, k, 0, head.next);
return head;
} else if (k == 1) {
tail = current.next;
return current;
} else {
Node<Integer> n = kReverseLinkedList(head, k - 1, 0, current.next);
current.next.next = current;
if (current == head)
head.next = tail;
return n;
}
}
// usage: kReverseLinkedList(myListHead, 8, 2, myListHead); (k >= 2, offset >= 0)
这里,我想递归地反转链表的每k个元素。对于链表
3 → 4 → 5 → 2 → 6 → 1 → 9
对于 kReverse(3)
变为 5 → 4→ 3→ 1→ 6→ 2→ 9→ 1
我收到 NullPointerException
.
public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k, int size) {
if(size<k) {
return ReverseLinkedList.reverseLinkedList(head);
}
Node<Integer> temp = head;
int i=1;
while(i<k) {
temp = temp.next;
i++;
}
Node<Integer> newHead = temp;
temp.next=null;
ReverseLinkedList.reverseLinkedList(head);
Node<Integer> smallerHead = kReverseLinkedList(head.next, k, size-k);
head.next = smallerHead;
return newHead;
}
粗略地看一下,您没有更新递归来使用 newHead。
此外,你需要注意打破和制造指针。当您保留前 3 个元素时,它们需要指向它们的前一个。
4.next = 3 和 5.next = 4(您需要在代码中进行管理)
一个提示:
使用大小为 k 的 堆栈会容易得多,它会递归地反转所需的元素并在其满时弹出。
我不确定这是不是你想要的? 不需要尺寸,
public class Node<T> {
private T item;
private Node<T> next;
public Node(T item, Node<T> next) {
this.item = item;
this.next = next;
}
public Node(T item) {
this.item = item;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> next) {
this.next = next;
}
public static Node<Integer> reverseLinkedList(Node<Integer> head) {
if (head.next != null){
Node<Integer> prev = head.next;
Node<Integer> result = reverseLinkedList(prev);
prev.next = head;
return result;
} else {
return head;
}
}
private static Node<Integer> kReverseLinkedList(Node<Integer> head, Node<Integer> cursor, int counter, int k) {
Node<Integer> result;
if (cursor.next == null){
result = reverseLinkedList(head);
head.next = null;
} else if (counter > 0){
result = kReverseLinkedList(head, cursor.next, counter-1, k);
} else {
Node<Integer> next = cursor.next;
cursor.next = null;
result = reverseLinkedList(head);
head.next = kReverseLinkedList(next, next, k, k);
}
return result;
}
public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k) {
Node<Integer> result = null;
if (head != null){
result = head;
if (k > 1) {
result = kReverseLinkedList(head, head, k-1, k-1);
}
}
return result;
}
public static void print(Node<Integer> n) {
if (n != null){
System.out.print(n.item+" ");
print(n.next);
} else {
System.out.println();
}
}
public static void main(String[] args) {
int[] data = {3,4,5,2,6,1,9};
Node<Integer> head = new Node<>(data[0]);
Node<Integer> tail = head;
for (int i = 1; i < data.length; i++) {
Node<Integer> n = new Node<>(data[i]);
tail.setNext(n);
tail = n;
}
print(head);
head = kReverseLinkedList(head, 3);
print(head);
}
}
输出:
3 4 5 2 6 1 9
5 4 3 1 6 2 9
我认为递归版本中不需要循环。
要使其通用,请添加一个偏移量。
不需要尺寸。
这里是带偏移量的真实递归版本(未测试):
private static Node<Integer> tail;
public static Node<Integer> kReverseLinkedList(Node<Integer> head, int k, int offset, Node<Integer> current) {
if (offset > 1) {
kReverseLinkedList(head.next, k, offset - 1, head.next);
return head;
} else if (offset == 1) {
head.next = kReverseLinkedList(head.next, k, 0, head.next);
return head;
} else if (k == 1) {
tail = current.next;
return current;
} else {
Node<Integer> n = kReverseLinkedList(head, k - 1, 0, current.next);
current.next.next = current;
if (current == head)
head.next = tail;
return n;
}
}
// usage: kReverseLinkedList(myListHead, 8, 2, myListHead); (k >= 2, offset >= 0)