如何递归查找链表中倒数第二个 Char 出现？

Question

作为家庭作业，我假设 return 字母倒数第二个出现的位置——以了解要检查的字母是作为 Char 类型参数传递的。我正在搜索的是一个自编码链表。它还必须递归完成，我一直在努力完全理解这一点。这是我到目前为止所做的。

注意：如果字母出现 0 次或 1 次，return -1。

例如 ["ababcdefb"].positionOfSecondToLastOccurrence('b') == 3

static class Node {
        public Node (char item, Node next) { this.item = item; this.next = next; }
        public char item;
        public Node next;
    }

Node first;

public int positionOfSecondToLastOccurrence (char letter) {

        if (first == null)
            return -1;

        return positionOfSecondToLastOccurrenceHelper(letter, first, 0);
    }

private int positionOfSecondToLastOccurrenceHelper(char c, Node n, int pos) {

        if (n.next == null)
            return n.item;

        return pos += compare(n.item, positionHelper(c, n.next, pos));

    }

private int compare(char c, int p) {

        int result = 0;

        if (c == p)
            return result += 1;

        return 0;
    }

我明白为什么这不起作用；我 return 得到 1 的结果，然后在返回上一个函数调用时将其与 n.item 进行比较，这永远不会是真的。我不知道的是如何使这项工作。任何指导都会很棒。

Answer 1

我会分步进行。我会先写一个 positionOfLastOccurrence(char letter)。将此编写为递归方法应该会教给您一些 positionOfSecondToLastOccurrence().

也需要的技术

接下来的大部分挑战在于辅助方法的良好设计。我想我会写一个 positionOfLastOccurrenceBeforePosition(int pos, char letter) 应该 return 最后一次出现的 letter 的位置严格在位置 pos 之前。因此，根据您的示例列表，ababcdefb、positionOfLastOccurrenceBeforePosition(0, 'b') 会 return -1，positionOfLastOccurrenceBeforePosition(2, 'b') 会产生 1，positionOfLastOccurrenceBeforePosition(100, 'b') 会产生 8。此方法也应该是递归的，我相信，因为这将是最终完成实际工作的人。

现在查找倒数第二个匹配项是先查找最后一个匹配项，然后再查找最后一个匹配项之前的匹配项。

Answer 2

你使用的是单向链表，也就是说你只能朝一个方向遍历，即向前，即从第一个节点到最后一个节点。

算法然后从第一个节点到最后一个节点遍历列表，并将每个节点的 item 与您要搜索的项目进行比较。此外，您还需要两个变量，它们将在您要搜索的项目的最后一次（即最终）和倒数第二次（即倒数第二）出现的列表中保存索引。这两个变量的初始值都应为 -1（减一）。

当您第一次出现所搜索的项目时，更新最终索引变量。当你命中下一个事件时，将倒数第二个索引设置为最终索引，然后更新最终索引。

对搜索项的每个后续出现重复，即将倒数第二个索引设置为最终索引，然后将最终索引设置为列表中当前节点的索引。因此，如果搜索的项目在列表中只出现一次，或者根本没有出现，倒数第二个索引将为 -1。

编写递归方法时，首先需要的是一些终止递归的条件。如果条件为真，return 一个合适的值。如果条件为假，则更改方法参数并使用修改后的参数调用相同的方法。你的终止条件是一个空节点。

由于列表不是数组，您还需要跟踪当前节点的索引，以便能够从您的递归方法中return它。

这是我的实现。我创建了一个 LinkList class，其中包含您的 Node class 的列表。 LinkList class 允许我最初创建一个链表。我还在 Node 和 LinkList class 中添加了方法 toString() 以帮助可视化列表的外观。 main() 方法作为递归方法的测试。递归方法的第一次调用使用列表中的第一个节点，其索引为 0（零）。

public class Penultim {

    public static void main(String[] args) {
        LinkList list = new LinkList();
        list.append('a');
        list.append('b');
        list.append('a');
        list.append('b');
        list.append('c');
        list.append('d');
        list.append('e');
        list.append('f');
        list.append('b');
        System.out.println(list);
        System.out.println(list.getPenultimateOccurrenceIndex('b', list.getHead(), 0, -1, -1));
    }
}

class Node {
    private char item;
    private Node next;

    public Node(char item, Node next) {
        this.item = item;
        this.next = next;
    }

    public char getItem() {
        return item;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public String toString() {
        return item + "->";
    }
}

class LinkList {
    private Node head;

    public void append(char item) {
        if (head == null) {
            head = new Node(item, null);
        }
        else if (head.getNext() == null) {
            head.setNext(new Node(item, null));
        }
        else {
            Node node = head.getNext();
            while (node != null) {
                if (node.getNext() == null) {
                    node.setNext(new Node(item, null));
                    break;
                }
                node = node.getNext();
            }
        }
    }

    public Node getHead() {
        return head;
    }

    public int getPenultimateOccurrenceIndex(char item,
                                             Node node,
                                             int ndx,
                                             int penultimate,
                                             int ultimate) {
        if (node == null) {
            return penultimate;
        }
        else {
            if (node.getItem() == item) {
                if (ultimate >= 0) {
                    penultimate = ultimate;
                }
                ultimate = ndx;
            }
            return getPenultimateOccurrenceIndex(item,
                                                 node.getNext(),
                                                 ndx + 1,
                                                 penultimate,
                                                 ultimate);
        }
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node node = head;
        while (node != null) {
            sb.append(node);
            node = node.getNext();
        }
        return sb.toString();
    }
}

以上代码运行时的输出为

a->b->a->b->c->d->e->f->b->
3

如何递归查找链表中倒数第二个 Char 出现？

How to find the second to last Char occurrence in a linked list recursively?

java

recursion

singly-linked-list