java - 将链表的所有其他元素(就地)移动到java中链表的末尾

Question

题目如下:给定一个 linked list，将备用 indices 移到 list

的后面

例如:

input:         :  [0] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7]
expected output:  [0] -> [2] -> [4] -> [6] -> [1] -> [3] -> [5] -> [7] /

正如您从预期输出中看到的那样，位于奇数位置(索引)的元素被移动到 linkedlist 的后面。我试图实现这个；我可以删除奇怪的索引，但它们没有链接到列表的末尾。

我的代码在这里:

public void shift(){
    if (front==null) return;

    ListNode curr=front;
    ListNode temp=curr.next;
    while (curr.next!=null && curr.next.next!=null){
        curr.next=curr.next.next;
        curr=curr.next;
        temp.next=curr.next;
     }
     curr.next=temp;
    temp.next=null;
}


expected output: front -> [0] -> [2] -> [4] -> [6] -> [1] -> [3] -> [5] -> [7] /
my output: front -> [0] -> [2] -> [4] -> [6] -> [1] /

我需要一些帮助

P.S:不得使用辅助存储。没有其他容器!!!所以这是一个就地重新安排

Answer 1

形成一个包含奇数索引元素的列表和另一个包含偶数索引元素的列表。将奇数列表附加到偶数列表。时间复杂度为O(n)，辅助空间复杂度为O(1)。

    public void shift() {
       if (front == null)
            return;
        ListNode oddList, even, odd;
        oddList = even = odd = front;
        oddList = front.next;
        while (even.next != null) {
            odd.next = even.next;
            odd = even.next;
            even.next = odd.next;
            if(odd.next != null) {
                even = odd.next;
                odd.next = null;
            } else {
                odd.next = null;
                break;
            }
        }
        if(oddList != null) {
            even.next = oddList;
        }
        //"front" points to the start of the new list.
   }