使用堆栈折叠链接列表

Question

下面是我使用Stack:折叠链接列表的程序

public Node middle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
public Node foldList(Node head){
Node mid = middle(head);
Node f = mid.next;
Stack<Node> stacks = new Stack<>();
if (head == null) return head;
while (f != null){
stacks.push(f);
f = f.next;
}
Node temp = head;
Node forv = head.next;
while(!stacks.isEmpty()) {
temp.next = stacks.pop();
temp = temp.next;
temp.next = forv;
temp = temp.next;
forv = forv.next;
}
return head;
}

下面是middle((和foldList((方法的代码。当我运行它时，它会陷入一个无限循环。有人能帮我找出为什么会发生这种事吗？

Answer 1

问题是您正在执行以下操作：

linked list: 1-2-3-4-5-6

将后半部分放入堆栈：

linked list: 1-2-3-4-5-6
stack: 5-6    

在链表节点之间插入堆栈节点：

linked list: 1-6-2-3-4-5-6-2-3-4-5-6-2-3-4-5-6.....infinite

在开始折叠之前，您需要从链表中删除后半部分节点(放在堆栈上的节点(。

由于它是一个链表，您可以简单地取消mid.next：

public Node foldList(Node head){
Node mid = middle(head);
Node f = mid.next;
// remove the second half
mid.next = null
Stack<Node> stacks = new Stack<>();
if (head == null) return head;
while (f != null){
stacks.push(f);
f = f.next;
}

以下是我的完整代码，使用Deque而不是Stack(因为Stack又旧又发霉(：

import java.util.ArrayDeque;
import java.util.Deque;
public class LinkedListFolder {
public static void main(String[] args) {
Node head = createLinkedList();
foldList(head);
print(head);
}
private static Node createLinkedList() {
Node head = new Node(1);
Node current = head;
for (int i = 2; i < 7; i++) {
current.next = new Node(i);
current = current.next;
}
return head;
}
private static void print(Node node) {
System.out.println(node);
while (node.next != null) {
node = node.next;
System.out.println(node);
}
}
public static void foldList(Node head) {
if (head == null) {
return;
}
Deque<Node> nodesToFold = getNodesToFold(head);
Node current = head;
Node successor = head.next;
while (!nodesToFold.isEmpty()) {
current.next = nodesToFold.pop();
current = current.next;
current.next = successor;
current = current.next;
successor = successor.next;
}
}
private static Deque<Node> getNodesToFold(Node head) {
Node middle = findMiddle(head);
Node current = middle.next;
middle.next = null;
Deque<Node> nodesToFold = new ArrayDeque<>();
while (current != null) {
nodesToFold.push(current);
current = current.next;
}
return nodesToFold;
}
public static Node findMiddle(Node head) {
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

static class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return String.format("Node{value=%d}", value);
}
}
}

输出：

Node{value=1}
Node{value=6}
Node{value=2}
Node{value=5}
Node{value=3}
Node{value=4}