考虑：
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?
我似乎无法理解这一点以及它是如何逆转的。有人可以解释一下这是如何工作的吗？
您迭代地反转列表，并且始终正确反转区间 [head, previous] 中的列表（因此当前是第一个未正确设置其链接的节点）。在每个步骤中，您都执行以下操作：
如果您对所有节点都这样做，您可以证明（例如通过归纳）列表将被正确反转。
代码只是遍历列表并反转链接，直到它到达前一个尾部，它作为新的头部返回。
前：
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;
}
我称之为“樱桃采摘”。这个想法是最小化掉期的数量。交换发生在近索引和远索引之间。这是一个twp-pass算法。
(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
考虑它的最简单方法是这样思考：
图表：
最初：
Original List -> 1 2 3 4 5
New List -> null
第一次迭代
Original List -> 1 2 3 4 5
New List -> 1->null [head shifted to left, now newHead contains 1 and points to null]
第二次迭代
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]
第三次迭代
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;
}
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 the 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;
}
使用迭代反转单链表：
current = head // Point the current pointer to the 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 the current pointer is the head pointer it should point to NULL while reversing
current = current->link; // Traversing the list
}
head = current; // Make the current pointer the head pointer
基本思想是从第一个列表中分离头节点并将其附加到第二个列表的头。不断重复，直到第一个列表为空。
伪代码：
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;
}
这是一个反转单链表的简单函数
// Defining Node structure
public class Node {
int value;
Node next;
public Node(int val) {
this.value=val;
}
}
public LinkedList reverse(LinkedList list) {
if(list==null) {
return list;
}
Node current=list.head;
Node previous=null;
Node next;
while(current!=null) {
next=current.next;
current.next=previous;
previous=current;
current=next;
}
list.head=previous;
return list;
}
为了更好地理解，您可以观看此视频https://youtu.be/6SYVz-pnVwg
如果要使用递归：
class Solution {
ListNode root=null;
ListNode helper(ListNode head)
{
if (head.next==null)
{ root= head;
return head;}
helper (head.next).next=head;
head.next=null;
return head;
}
public ListNode reverseList(ListNode head) {
if (head==null)
{
return head;
}
helper(head);
return root;
}
}