java如何将一个链表分离成两个其他的列表，一个是奇数索引，另一个是偶数索引，但以递归的方式

Question

该问题要求编写一个函数，该函数可以将链表拆分为另外两个列表，一个具有奇数索引，另一个具有偶数索引，但是递归的。我已经阅读了stack overflow中所有类似的问题，但它们没有递归方式

以下是我的尝试：

public class LinkedList {
Node head;
static int count = 0;
static LinkedList oddList = new LinkedList();
static LinkedList evenList = new LinkedList();

static class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}

public static void split(Node head) {

    if (head == null) return;
    split(head.next);
    if ((++count) % 2 == 0) {
        insert(evenList, head.data);
    } else
        insert(oddList, head.data);
}

这个程序只是递归地遍历而不是插入，我不知道如何遍历和插入两个链表中的元素

你能帮我写那个函数来做那个工作吗

Answer 1

伪代码：

TwoLists splitEvenAndOddIndices(List originalList) {
    if (originalList.isEmpty()) {
        return two empty lists;
    }
    Element head = remove the head (the frontmost element) from originalList;
    TwoLists result = splitEvenAndOddIndices(originalList);
    Swap the two lists in result;
    Prepend head to the first list in result,
    return result;
}