Блог

В leetcode есть проблема, называемая нечетным четным связанным списком.

В нем говорится:

Учитывая односвязный список, сгруппируйте все нечетные узлы вместе, за которыми следуют четные узлы. Пожалуйста, обратите внимание, что здесь мы говорим о номере узла, а не о значении в узлах.

Вы должны попытаться сделать это на месте. Программа должна выполняться с O (1) пространственной сложностью и O (nodes) временной сложностью.

Пример: Дано 1->2->3->4->5-> NULL, возврат 1->3->5->2->4-> НОЛЬ.

Вот мой класс узла

 public class Node 
{
private int value;
private Node next;

public Node(int Value) 
{
    this.value = Value;
    this.next = null;
}

public Node()
{
    this.value = -1;
    this.next = null;
}

public Node getNext() {
    return next;
}public void setNext(Node next) {
    this.next = next;
}public int getValue() {
    return value;
}public void setValue(int value) {
    this.value = value;
}
}
 

Я получил 8 элементов в списке, которые имеют значения 1,2,3,4,5,6,7,8. Это мой вывод —>1—>3—>5—>7—>2—>4—>6—>8
И вот мой метод связанного списка для решения задачи OddEven.

 public void oddEven()
{
    if(head.getNext() == null)
        return;

    Node lastOdd = head.getNext(); // gets the value of last odd even in list.
    Node current = lastOdd.getNext(); // Puts the reference on the first even index.
    Node before = lastOdd; // This node, will always be one index before current Node
    int travel = 1, loop;


    while(current != null)
    {
        loop = travel;
        // Prvo petlja putuje do sledeceg neparnog elementa
        while(loop-- > 0)
        {
            before = current;
            current = current.getNext();
        }

        if(current == null) // If it is end of the list, exit loop.
            break;

        before.setNext(current.getNext());
        current.setNext(lastOdd.getNext());
        lastOdd.setNext(current);
        lastOdd = current;
        current = before.getNext();

    }

}
 

Он отлично работает на моем компьютере. Но когда я помещаю код в leetcode, я получаю сообщение об ошибке, что он не работает. Но это тот же код. Вот код из leetcode

  /**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
  public class Solution {
   public ListNode oddEvenList(ListNode head) 
{

    if(head.next == null)
        return head;

    ListNode lastOdd = head.next; // gets the value of last odd even in list.
    ListNode current = lastOdd.next; // Puts the reference on the first even index
    ListNode before = lastOdd;
    int travel = 1, loop;


    while(current != null)
    {
        loop = travel;
        // Prvo petlja putuje do sledeceg neparnog elementa
        while(loop-- > 0)
        {
            before = current;
            current = current.next;
        }

        if(current == null)
            break;



        before.next = current.next;
        current.next = lastOdd.next;
        lastOdd.next = current;
        lastOdd = current;
        current = before.next;

    }
    return head;
}
}
 

Вот ошибка, которую я получаю

для ввода:[1,2,3,4,5,6,7,8]

Ваш ответ: [1,2,4,6,8,3,5,7]

Ожидаемый ответ: [1,3,5,7,2,4,6,8]

Но это тот же метод, где я допустил ошибку?

Я зашел на сайт и вставил ваш код, чтобы было легче понять, что происходит, проблема в этой строке:

 ListNode lastOdd = head.next; // gets the value of last odd even in list.
 

Первый элемент списка равен 1, но вы начинаете последнее нечетное число как следующее в списке, а не начало списка. Просто меняю это на:

 ListNode lastOdd = head
 

и он дает правильный ответ.

Сам код нуждается в некоторой уборке, внутренний цикл while, похоже, не служит никакой реальной цели, не уверен, почему это там или это оставшийся элемент предыдущей попытки?

Что loop и travel переменные делают? Они постоянны в 1 на каждой итерации, тогда зачем while(loop-- > 0) цикл. Извините, не понял, чего вы пытаетесь достичь с помощью этого цикла.

 int travel = 1, loop;
    while(current != null)
    {
        loop = travel;
        // Prvo petlja putuje do sledeceg neparnog elementa
        while(loop-- > 0)
        {
 

Решение: найдите последний узел в списке. Переместите все четно расположенные узлы в конец, выполнив append . Убедитесь, что вы остановились на узле, отмеченном как последний на первом шаге, иначе он запустится в бесконечный цикл.