Ответ 1
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;
}
Как именно он меняет список? Я понимаю, что он сначала устанавливает второй node на forward
. Тогда он говорит, что current.next
равно a null
node previous
. Затем он говорит, что previous
теперь current
. Наконец current
становится forward
?
Я не могу понять этого и как его реверсирование. Может кто-нибудь объяснить, как это работает?
Вы изменяете список итеративно и всегда имеете правильный список в интервале [head, previous] (так что текущий - это первый node, который неправильно установил ссылку). На каждом шаге вы делаете следующее:
Если вы сделаете это для всех узлов, которые вы можете доказать (например, с индукцией). Что список будет правильно отменен.
Код просто просматривает список и инвертирует ссылки до тех пор, пока не достигнет предыдущего хвоста, который он возвращает в качестве новой главы.
До:
Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null
После:
null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head)
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;
}
Я называю это "подбор вишни" . Идея состоит в том, чтобы свести к минимуму количество свопов. Переключение происходит между индексом ближнего и дальнего. Его алгоритм с двумя проходами.
(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
Реверсирование одного связанного списка с использованием итерации
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
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;
}
Основная идея состоит в том, чтобы отсоединить голову 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
//реализация функции обращения по односвязному списку
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;
}
Самый простой способ думать об этом - думать так:
Диаграмма:
Первоначально:
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;
}