Как перевернуть связанный список?

Question

 Node reverse(Node head) {
    Node previous = null;
    Node current = head;
    Node forward;

    while (current != null) {
        forward = current.next;
        current.next = previous;
        previous = current;
        current = forward;
    }

    return previous;
}

Как именно он переворачивает список? Я получаю, что он сначала устанавливает второй узел на forward. Затем он говорит, что current.next равно null узлу previous. Тогда это говорит, что previous теперь current. Наконец current становится forward?

Кажется, я не могу понять, как это изменилось. Может кто-нибудь объяснить, как это работает?

Answer 1

Answer 2

public Node getLastNode( )
{
    if( next != null )
        return next.getLastNode( );
    else
        return this;
}

public Node reverse( Node source )
{
    Node reversed = source.getLastNode( );
    Node cursor = source;

    while( cursor != reversed )
    {
        reversed.addNodeAfter( cursor.getInfo( ) );
        cursor = cursor.getNodeAfter( );
    }

    source = reversed;
    return source;
}

Answer 3

Код просто перемещается по списку и инвертирует ссылки, пока не достигнет предыдущего хвоста, который возвращается как новый заголовок.

До:

Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null

После:

   null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head)

Answer 4

Вы переворачиваете список итеративно и всегда получаете список в интервале [head, previous] правильно перевернутым (таким образом, current - это первый узел, у которого ссылка установлена ​​неправильно). На каждом шаге вы делаете следующее:

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

Если вы сделаете это для всех узлов, которые вы можете доказать (например, с помощью индукции). Что список будет правильно перевернут.

Answer 5

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

    (Odd length)  A -> B -> C -> D -> E
    (Even length) A -> B -> C -> D

    Pre-Condition: N >= 2

    Pass 1: Count N, the number of elements

    Pass 2: 
            for(j=0 -> j<= (N/2 -1))
            {
              swap(j, (N-1)-j)
            }

Пример 1 :

   For above Odd length list, N = 5 and there will be two swaps 

      when j=0, swap(0, 4) //post swap state: E B C D A
      when j=1, swap(1, 3) //post swap state: E D C B A


   The mid point for odd length lists remains intact.

Пример 2 :

   For above Even length list, N = 4 and there will be two swaps 

      when j=0, swap(0, 3) //post swap state: D B C A
      when j=1, swap(1, 2) //post swap state: D C B A

• Подстановка применяется только к данным, а не к указателям, могут быть пропущены любые проверки работоспособности, но вы поняли идею.

Answer 6

Самый простой способ думать об этом - думать следующим образом:

1. Сначала добавьте заголовок списка в новый связанный список.
2. Продолжайте перебирать оригинал ипродолжайте добавлять узлы перед заголовком нового связанного списка.

Диаграмма:

Изначально:

Original List -> 1 2 3 4 5
New List -> null

1-я итерация

Original List -> 1 2 3 4 5
New List -> 1->null [head shifted to left, now newHead contains 1 and points to null]

2-я итерация

Original List -> 1 2 3 4 5
New List -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

3-я итерация

Original List -> 1 2 3 4 5
New List ->3 -> 2-> 1->null [head shifted to left, now newHead contains 2 and points to next node which is 1]

Теперь этопродолжает цикл до конца.Итак, наконец, новый список становится:

  New List->  5 -> 4 -> 3 -> 2 -> 1 -> null

Код для того же должен быть таким (это было легко понять):

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

public ListNode reverseList(ListNode head) {
    if(head == null) {
        return null;
    }

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

    ListNode current = head;
    ListNode previous = new ListNode(head.val);
    previous.next = null;

    while(current.next != null) {
        current = current.next;
        previous = addBeforeHead(current, previous);
    }

    return previous;
}

private ListNode addBeforeHead(ListNode node, ListNode head) {
    if (node == null) return null;
    ListNode temp = new ListNode(node.val);

    temp.next = head;
    head = temp;

    return head;
}

Answer 7

// реализация функции обращения односвязных списков

struct Node
{
    int data;
    struct Node* link;
}
Node* head = NULL;

void reverseList()
{
    Node* previous, *current, *next;
    previous = NULL;
    current = head;

while(current != NULL)
{
    next = current-> link;
    current->link = previous;
    previous = current;
    current = next;
}

    head = previous;
}

Answer 8

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

Псевдокод:

function reverseList(List X) RETURNS List
   Y = null
   WHILE X <> null
      t = X.next
      X.next = Y
      Y = X
      X = t
   ENDWHILE
   RETURN Y
ENDfunction

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

function reverseList(List X) RETURNS List
   RETURN reverseListAux(X, null)
ENDfunction

function reverseListAux(List X, List Y) RETURNS List
   IF X = null THEN
       RETURN Y
   ELSE
       RETURN reverseListAux(X.next, makeNode(X.data, Y))
ENDfunction

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

function reverseList(List X) RETURNS List
   Y = null
   WHILE X <> null
     Y = makeNode(x.data, Y)
     X = X.next   
   ENDWHILE
   RETURN Y
ENDfunction

Answer 9

  list_t *reverse(list_t *a)
  {
    list_t *progress = NULL;
    while(a)
    {
      list_t *b; //b is only a temporary variable (don't bother focusing on it)
      b = a->next;
      a->next = progress; //because a->next is assigned to another value, we must first save a->next to a different variable (to be able to use it later)
      progress = a; //progress is initially NULL (so a->next = NULL (because it is the new last element in the list))
      a = b; //we set a to b (the value we saved earlier, what a->next was before it became NULL)
      /*
        now, at next iteration, progress will equal a, and a will equal b.
        so, when I assign a->next = progress, I really say, b->next = a.
        and so what we get is: b->a->NULL.
        Maybe that gives you an idea of the picture?
        What is important here is:
          progress = a
        and
          a = b
        Because that determines what a->next will equal:
          c->b->a->0
        a's next is set to 0
        b's next is set to a
        c's next is set to b
      */
    }
    return progress;
  }

Answer 10

Сторнирование односвязного списка с использованием итерации

current = head //point current pointer to head of the linked list

while(current != NULL)
{
forward = current->link; //point to the next node
fforward = forward->link; //point the next node to next node
fforward->link = forward;//1->2->3,,,,,,,,,this will point node 3 to node 2
forward->link = current; //this will point node 2 to node 1
if(current == head)
current->link = NULL;// if current pointer is head pointer it should point to NULL while reversing

current = current->link; //traversing the list
}
head = current; //make current pointer the head pointer