使用 Stack 折叠链表

Question

这是我使用堆栈折叠链表的程序：

    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}

使用 Stack 折叠链表

Folding a linked list using a Stack

java

linked-list

data-structures

singly-linked-list