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

Ответ 1

Ответ 2

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

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

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

Ответ 3

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

До:

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

После:

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

Ответ 4

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;
}

Ответ 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

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

Ответ 6

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

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

Ответ 7

  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 next is set to 0
        b next is set to a
        c next is set to b
      */
    }
    return progress;
  }

Ответ 8

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

псевдокод:

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

Ответ 9

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

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;
}

Ответ 10

Самый простой способ думать об этом - думать так:

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;
}