вычитание узлов связанного списка

Question

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

новое значение

1-го узла = значение последнего узла - текущее значение первого узла

новое значение 2-го узла = значение второго последнего узла - второй текущее значение узла

Пример:

Учитывая связанный список 1 -> 2 -> 3 -> 4 -> 5,

Вы должны вернуть 4 -> 2 -> 3 -> 4 -> 5

До сих пор решения, которое я мог думать о

1. итерирует LinkedList, чтобы найти длину.
2. Итерировать вторую половину связанного списка, чтобы нажимать значения узлов в стек
3. Итерировать первую половину списка, поместить стек, вычесть значения узлов.

Возможно, это самое наивное решение. Может ли annyone предложить более эффективное решение с точки зрения времени/пространства (хотите избежать нескольких итераций и дополнительного места для стека)? Заранее спасибо.

Ответ:

public ListNode subtract(ListNode a) { 

     ListNode slow =a; 
     ListNode fast=a; 


     ListNode head = a; 

     ListNode middle = null; 

     while(fast!=null && fast.next!=null) 
      { 

       if(fast.next.next!=null) // in case numOfNodes are even , we need to stay at middle 
        slow=slow.next; 
       fast = fast.next.next; 

      } 
     if(slow==fast) 
      return a; 

     middle = slow; 
     ListNode secondHalf = middle.next; 
     middle.next = null; 

     ListNode reversed = reverse(secondHalf); 

     ListNode temp1 = reversed; 

     while(temp1!=null){ 
      head.val = temp1.val - head.val; 
      temp1 = temp1.next; 
      head = head.next; 
     } 

     middle.next = reverse(reversed); 


     return a; 

    } 


    public ListNode reverse(ListNode head){ 
     ListNode current = head; 
     ListNode previous = null; 

     while(current!=null) { 
      ListNode temp = current.next; 
      current.next = previous; 
      previous = current; 
      current = temp; 

     } 

     return previous; 
    } 

Answer 1

Если разрешено изменить список, то есть лучшее решение с постоянным дополнительным пространством, чем я упомянул в комментариях:

1. Найти середину ,

2. Обратный список от середины вправо.

3. Выполнение вычитаний путем перехода по двум спискам шаг за шагом.

4. Обратно/присоединяйтесь к спискам назад, чтобы получить исходный список заказов.

Все эти шаги требуют вывода (1) пространство и О (п), следовательно, алгоритм в целом также требует O (1) пространство и О (п) времени.

Это только набросок алгоритма, чтобы доказать, что это возможно в O (N) время с constanst дополнительным пространством, есть некоторые ловушки, как четное/нечетное число элементов и т.д.

Там может быть некоторыми комната для улучшений, но вы не можете улучшить время O (n), потому что для поиска последнего элемента или выполнения вычитаний уже требуется O (n) время.

Answer 2

Вы можете написать рекурсивную функцию, которая позволит решить эту проблему без дополнительного пространства, если вы не считаете фрейм стека лишним.

Код написан на C#, но вы должны иметь возможность легко перевести его на необходимый вам язык.

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

static ListNode<int> temp = list.head; // Point to first element in the list 
private static int reverse(ListNode<int> listNode, int currentNode, int totalNodes) 
{ 
    if (listNode == null) 
    { 
     return 0; 
    } 
    currentNode = reverse(listNode.next, currentNode, totalNodes + 1); 
    if (currentNode < totalNodes) //To check if half is reached 
    { 
     temp.data = listNode.data - temp.data; 
     temp = temp.next; 
    } 
    return ++currentNode; 
} 

Вы можете вызвать этот метод как таковой reverse(list.head, 0, 0); и игнорировать возвращаемое значение или хранить его где-нибудь, как это указывает на середине связанного списка, который может быть полезен где-то позже.

Со стандартным внедрением связанного списка я сомневаюсь, что вы сможете достичь космической/временной сложности лучше, чем это.

Вы можете заменить глобальную переменную и передать ее в качестве аргумента, если вы можете изменить реализацию ListNode, чтобы включить индекс этого узла.