我想知道是否存在一些逻辑来反转仅使用两个指针的单链表。
以下用于使用三个指针反转单链表，即p, q, r：
struct node {
int data;
struct node *link;
};
void reverse() {
struct node *p = first,
*q = NULL,
*r;
while (p != NULL) {
r = q;
q = p;
p = p->link;
q->link = r;
}
first = q;
}
是否有任何其他替代方案来反转链表？就时间复杂度而言，反转单链表的最佳逻辑是什么？
有什么选择吗？不，这很简单，并且没有根本不同的方法。这个算法已经是 O(n) 时间了，你不能比这更快，因为你必须修改每个节点。
看起来您的代码在正确的轨道上，但它并不能完全按照上面的形式工作。这是一个工作版本：
#include <stdio.h>
typedef struct Node {
char data;
struct Node* next;
} Node;
void print_list(Node* root) {
while (root) {
printf("%c ", root->data);
root = root->next;
}
printf("\n");
}
Node* reverse(Node* root) {
Node* new_root = 0;
while (root) {
Node* next = root->next;
root->next = new_root;
new_root = root;
root = next;
}
return new_root;
}
int main() {
Node d = { 'd', 0 };
Node c = { 'c', &d };
Node b = { 'b', &c };
Node a = { 'a', &b };
Node* root = &a;
print_list(root);
root = reverse(root);
print_list(root);
return 0;
}
我讨厌成为坏消息的传递者，但我认为你的三分球解决方案实际上并不奏效。当我在以下测试工具中使用它时，列表被减少到一个节点，根据以下输出：
==========
4
3
2
1
0
==========
4
==========
您不会得到比您的解决方案更好的时间复杂度，因为它是 O(n) 并且您必须访问每个节点来更改指针，但是您可以很容易地用两个额外的指针完成一个解决方案，如下面的代码所示：
#include <stdio.h>
// The list element type and head.
struct node {
int data;
struct node *link;
};
static struct node *first = NULL;
// A reverse function which uses only two extra pointers.
void reverse() {
// curNode traverses the list, first is reset to empty list.
struct node *curNode = first, *nxtNode;
first = NULL;
// Until no more in list, insert current before first and advance.
while (curNode != NULL) {
// Need to save next node since we're changing the current.
nxtNode = curNode->link;
// Insert at start of new list.
curNode->link = first;
first = curNode;
// Advance to next.
curNode = nxtNode;
}
}
// Code to dump the current list.
static void dumpNodes() {
struct node *curNode = first;
printf ("==========\n");
while (curNode != NULL) {
printf ("%d\n", curNode->data);
curNode = curNode->link;
}
}
// Test harness main program.
int main (void) {
int i;
struct node *newnode;
// Create list (using actually the same insert-before-first
// that is used in reverse function.
for (i = 0; i < 5; i++) {
newnode = malloc (sizeof (struct node));
newnode->data = i;
newnode->link = first;
first = newnode;
}
// Dump list, reverse it, then dump again.
dumpNodes();
reverse();
dumpNodes();
printf ("==========\n");
return 0;
}
此代码输出：
==========
4
3
2
1
0
==========
0
1
2
3
4
==========
我认为这就是你所追求的。它实际上可以做到这一点，因为一旦你加载first到遍历列表的指针中，你就可以随意重用first。
#include <stddef.h>
typedef struct Node {
struct Node *next;
int data;
} Node;
Node * reverse(Node *cur) {
Node *prev = NULL;
while (cur) {
Node *temp = cur;
cur = cur->next; // advance cur
temp->next = prev;
prev = temp; // advance prev
}
return prev;
}
这是在 C 中反转单链表的代码。
这里粘贴在下面：
// reverse.c
#include <stdio.h>
#include <assert.h>
typedef struct node Node;
struct node {
int data;
Node *next;
};
void spec_reverse();
Node *reverse(Node *head);
int main()
{
spec_reverse();
return 0;
}
void print(Node *head) {
while (head) {
printf("[%d]->", head->data);
head = head->next;
}
printf("NULL\n");
}
void spec_reverse() {
// Create a linked list.
// [0]->[1]->[2]->NULL
Node node2 = {2, NULL};
Node node1 = {1, &node2};
Node node0 = {0, &node1};
Node *head = &node0;
print(head);
head = reverse(head);
print(head);
assert(head == &node2);
assert(head->next == &node1);
assert(head->next->next == &node0);
printf("Passed!");
}
// Step 1:
//
// prev head next
// | | |
// v v v
// NULL [0]->[1]->[2]->NULL
//
// Step 2:
//
// prev head next
// | | |
// v v v
// NULL<-[0] [1]->[2]->NULL
//
Node *reverse(Node *head)
{
Node *prev = NULL;
Node *next;
while (head) {
next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
Robert Sedgewick，“ C 中的算法”，Addison-Wesley，第 3 版，1997，[第 3.4 节]
如果这不是循环列表，则 NULL 是最后一个链接。
typedef struct node* link;
struct node{
int item;
link next;
};
/* you send the existing list to reverse() and returns the reversed one */
link reverse(link x){
link t, y = x, r = NULL;
while(y != NULL){
t = y->next;
y-> next = r;
r = y;
y = t;
}
return r;
}
是的。我相信您可以像交换两个数字而不使用第三个数字一样执行此操作。只需将指针转换为 int/long 并执行几次 XOR 操作。这是一个有趣的问题，但没有任何实际价值的 C 技巧之一。
你能降低 O(n) 复杂度吗？不，不是。如果您认为需要相反的顺序，只需使用双向链表。
只是为了好玩（尽管尾递归优化应该阻止它吃掉所有的堆栈）：
Node* reverse (Node *root, Node *end) {
Node *next = root->next;
root->next = end;
return (next ? reverse(next, root) : root);
}
root = reverse(root, NULL);
要在不使用临时变量的情况下交换两个变量，
a = a xor b
b = a xor b
a = a xor b
最快的方法是写在一行
a = a ^ b ^ (b=a)
相似地，
使用两个交换
swap(a,b)
swap(b,c)
使用异或的解决方案
a = a^b^c
b = a^b^c
c = a^b^c
a = a^b^c
一站式解决方案
c = a ^ b ^ c ^ (a=b) ^ (b=c)
b = a ^ b ^ c ^ (c=a) ^ (a=b)
a = a ^ b ^ c ^ (b=c) ^ (c=a)
相同的逻辑用于反转链表。
typedef struct List
{
int info;
struct List *next;
}List;
List* reverseList(List *head)
{
p=head;
q=p->next;
p->next=NULL;
while(q)
{
q = (List*) ((int)p ^ (int)q ^ (int)q->next ^ (int)(q->next=p) ^ (int)(p=q));
}
head = p;
return head;
}
您需要一个跟踪列表的跟踪指针。
你需要两个指针：
选择第一个节点的 第一个指针。第二个指针选择第二个节点。
加工 ：
移动轨迹指针
将第二个节点指向第一个节点
通过将第二个指针分配给第一个指针，将第一个指针移动一步
将秒指针移动一步，通过将轨道指针分配给秒
Node* reverselist( )
{
Node *first = NULL; // To keep first node
Node *second = head; // To keep second node
Node *track = head; // Track the list
while(track!=NULL)
{
track = track->next; // track point to next node;
second->next = first; // second node point to first
first = second; // move first node to next
second = track; // move second node to next
}
track = first;
return track;
}
更具可读性如何：
Node *pop (Node **root)
{
Node *popped = *root;
if (*root) {
*root = (*root)->next;
}
return (popped);
}
void push (Node **root, Node *new_node)
{
new_node->next = *root;
*root = new_node;
}
Node *reverse (Node *root)
{
Node *new_root = NULL;
Node *next;
while ((next = pop(&root))) {
push (&new_root, next);
}
return (new_root);
}
这是Java中的一个更简单的版本。它确实只使用两个指针curr&prev
public void reverse(Node head) {
Node curr = head, prev = null;
while (head.next != null) {
head = head.next; // move the head to next node
curr.next = prev; //break the link to the next node and assign it to previous
prev = curr; // we are done with previous, move it to next node
curr = head; // current moves along with head
}
head.next = prev; //for last node
}
算出你现在使用的算法的时间复杂度，应该很明显它无法改进。
#include <stdio.h>
#include <malloc.h>
tydef struct node
{
int info;
struct node *link;
} *start;
void main()
{
rev();
}
void rev()
{
struct node *p = start, *q = NULL, *r;
while (p != NULL)
{
r = q;
q = p;
p = p->link;
q->link = r;
}
start = q;
}
我不明白为什么需要返回 head 因为我们将它作为参数传递。我们正在传递链接列表的头部，然后我们也可以更新。下面是简单的解决方案。
#include<stdio.h>
#include<conio.h>
struct NODE
{
struct NODE *next;
int value;
};
typedef struct NODE node;
void reverse(node **head);
void add_end(node **head,int val);
void alloc(node **p);
void print_all(node *head);
void main()
{
node *head;
clrscr();
head = NULL;
add_end( &head, 1 );
add_end( &head, 2 );
add_end( &head, 3 );
print_all( head );
reverse( &head );
print_all( head );
getch();
}
void alloc(node **p)
{
node *temp;
temp = (node *) malloc( sizeof(node *) );
temp->next = NULL;
*p = temp;
}
void add_end(node **head,int val)
{
node *temp,*new_node;
alloc(&new_node);
new_node->value = val;
if( *head == NULL )
{
*head = new_node;
return;
}
for(temp = *head;temp->next!=NULL;temp=temp->next);
temp->next = new_node;
}
void print_all(node *head)
{
node *temp;
int index=0;
printf ("\n\n");
if (head == NULL)
{
printf (" List is Empty \n");
return;
}
for (temp=head; temp != NULL; temp=temp->next,index++)
printf (" %d ==> %d \n",index,temp->value);
}
void reverse(node **head)
{
node *next,*new_head;
new_head=NULL;
while(*head != NULL)
{
next = (*head)->next;
(*head)->next = new_head;
new_head = (*head);
(*head) = next;
}
(*head)=new_head;
}
不，没有什么比当前的 O(n) 更快的了。您需要更改每个节点，因此时间将与元素数量成正比，这就是您已经拥有的 O(n)。
您可以仅借助一个额外的指针来解决此问题，对于反向功能，该指针必须是静态的。它的复杂度为 O(n)。
#include<stdio.h>
#include<stdlib.h>
typedef struct List* List;
struct List {
int val;
List next;
};
List reverse(List list) { /* with recursion and one static variable*/
static List tail;
if(!list || !list->next) {
tail = list;
return tail;
} else {
reverse1(list->next);
list->next->next = list;
list->next = NULL;
return tail;
}
}
使用两个指针同时保持 O(n) 的时间复杂度（最快可实现）可能只能通过指针的数字转换和交换它们的值来实现。这是一个实现：
#include <stdio.h>
typedef struct node
{
int num;
struct node* next;
}node;
void reverse(node* head)
{
node* ptr;
if(!head || !head->next || !head->next->next) return;
ptr = head->next->next;
head->next->next = NULL;
while(ptr)
{
/* Swap head->next and ptr. */
head->next = (unsigned)(ptr =\
(unsigned)ptr ^ (unsigned)(head->next =\
(unsigned)head->next ^ (unsigned)ptr)) ^ (unsigned)head->next;
/* Swap head->next->next and ptr. */
head->next->next = (unsigned)(ptr =\
(unsigned)ptr ^ (unsigned)(head->next->next =\
(unsigned)head->next->next ^ (unsigned)ptr)) ^ (unsigned)head->next->next;
}
}
void add_end(node* ptr, int n)
{
while(ptr->next) ptr = ptr->next;
ptr->next = malloc(sizeof(node));
ptr->next->num = n;
ptr->next->next = NULL;
}
void print(node* ptr)
{
while(ptr = ptr->next) printf("%d ", ptr->num);
putchar('\n');
}
void erase(node* ptr)
{
node *end;
while(ptr->next)
{
if(ptr->next->next) ptr = ptr->next;
else
{
end = ptr->next;
ptr->next = NULL;
free(end);
}
}
}
void main()
{
int i, n = 5;
node* dummy_head;
dummy_head->next = NULL;
for(i = 1; i <= n ; ++i) add_end(dummy_head, i);
print(dummy_head);
reverse(dummy_head);
print(dummy_head);
erase(dummy_head);
}
我有一个稍微不同的方法。我想利用现有函数（如 insert_at(index)、delete_from(index)）来反转列表（类似于右移操作）。复杂度仍然是 O(n)，但优点是更多的重用代码。看看 another_reverse() 方法，让我知道你们的想法。
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
struct node* head = NULL;
void printList(char* msg) {
struct node* current = head;
printf("\n%s\n", msg);
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
}
void insert_beginning(int data) {
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL)
{
head = newNode;
} else {
newNode->next = head;
head = newNode;
}
}
void insert_at(int data, int location) {
struct node* newNode = (struct node*) malloc(sizeof(struct node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL)
{
head = newNode;
}
else {
struct node* currentNode = head;
int index = 0;
while (currentNode != NULL && index < (location - 1)) {
currentNode = currentNode->next;
index++;
}
if (currentNode != NULL)
{
if (location == 0) {
newNode->next = currentNode;
head = newNode;
} else {
newNode->next = currentNode->next;
currentNode->next = newNode;
}
}
}
}
int delete_from(int location) {
int retValue = -1;
if (location < 0 || head == NULL)
{
printf("\nList is empty or invalid index");
return -1;
} else {
struct node* currentNode = head;
int index = 0;
while (currentNode != NULL && index < (location - 1)) {
currentNode = currentNode->next;
index++;
}
if (currentNode != NULL)
{
// we've reached the node just one prior to the one we want to delete
if (location == 0) {
if (currentNode->next == NULL)
{
// this is the only node in the list
retValue = currentNode->data;
free(currentNode);
head = NULL;
} else {
// the next node should take its place
struct node* nextNode = currentNode->next;
head = nextNode;
retValue = currentNode->data;
free(currentNode);
}
} // if (location == 0)
else {
// the next node should take its place
struct node* nextNode = currentNode->next;
currentNode->next = nextNode->next;
if (nextNode != NULL
) {
retValue = nextNode->data;
free(nextNode);
}
}
} else {
printf("\nInvalid index");
return -1;
}
}
return retValue;
}
void another_reverse() {
if (head == NULL)
{
printf("\nList is empty\n");
return;
} else {
// get the tail pointer
struct node* tailNode = head;
int index = 0, counter = 0;
while (tailNode->next != NULL) {
tailNode = tailNode->next;
index++;
}
// now tailNode points to the last node
while (counter != index) {
int data = delete_from(index);
insert_at(data, counter);
counter++;
}
}
}
int main(int argc, char** argv) {
insert_beginning(4);
insert_beginning(3);
insert_beginning(2);
insert_beginning(1);
insert_beginning(0);
/* insert_at(5, 0);
insert_at(4, 1);
insert_at(3, 2);
insert_at(1, 1);*/
printList("Original List\0");
//reverse_list();
another_reverse();
printList("Reversed List\0");
/* delete_from(2);
delete_from(2);*/
//printList();
return 0;
}
using 2-pointers....bit large but simple and efficient
void reverse()
{
int n=0;
node *temp,*temp1;
temp=strptr;
while(temp->next!=NULL)
{
n++; //counting no. of nodes
temp=temp->next;
}
// we will exchange ist by last.....2nd by 2nd last so.on....
int i=n/2;
temp=strptr;
for(int j=1;j<=(n-i+1);j++)
temp=temp->next;
// i started exchanging from in between ....so we do no have to traverse list so far //again and again for exchanging
while(i>0)
{
temp1=strptr;
for(int j=1;j<=i;j++)//this loop for traversing nodes before n/2
temp1=temp1->next;
int t;
t=temp1->info;
temp1->info=temp->info;
temp->info=t;
i--;
temp=temp->next;
//at the end after exchanging say 2 and 4 in a 5 node list....temp will be at 5 and we will traverse temp1 to ist node and exchange ....
}
}
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
};
struct node *first=NULL,*last=NULL,*next,*pre,*cur,*temp;
void create()
{
cur=(struct node*) malloc(sizeof(struct node));
printf("enter first data to insert");
scanf("%d",&cur->data);
first=last=cur;
first->link=NULL;
}
void insert()
{
int pos,c;
cur=(struct node*) malloc(sizeof(struct node));
printf("enter data to insert and also its position");
scanf("%d%d",&cur->data,&pos);
if(pos==1)
{
cur->link=first;
first=cur;
}
else
{
c=1;
next=first;
while(c<pos)
{
pre=next;
next=next->link;
c++;
}
if(pre==NULL)
{
printf("Invalid position");
}
else
{
cur->link=pre->link;
pre->link=cur;
}
}
}
void display()
{
cur=first;
while(cur!=NULL)
{
printf("data= %d\t address= %u\n",cur->data,cur);
cur=cur->link;
}
printf("\n");
}
void rev()
{
pre=NULL;
cur=first;
while(cur!=NULL)
{
next=cur->link;
cur->link=pre;
pre=cur;
cur=next;
}
first=pre;
}
void main()
{
int choice;
clrscr();
do
{
printf("Options are: -\n1:Create\n2:Insert\n3:Display\n4:Reverse\n0:Exit\n");
printf("Enter your choice: - ");
scanf("%d",&choice);
switch(choice)
{
case 1:
create();
break;
case 2:
insert();
break;
case 3:
display();
break;
case 4:
rev();
break;
case 0:
exit(0);
default:
printf("wrong choice");
}
}
while(1);
}
这是一个简单的解决方案......
void reverse()
{
node * pointer1 = head->next;
if(pointer1 != NULL)
{
node *pointer2 = pointer1->next;
pointer1->next = head;
head->next = NULL;
head = pointer1;
if(pointer2 != NULL)
{
while(pointer2 != NULL)
{
pointer1 = pointer2;
pointer2 = pointer2->next;
pointer1->next = head;
head = pointer1;
}
pointer1->next = head;
head = pointer1;
}
}
}
是的，有一种方法只使用两个指针。那就是通过创建新的链表，其中第一个节点是给定列表的第一个节点，第一个列表的第二个节点添加到新列表的开头，依此类推。
这是我的版本：
void reverse(ListElem *&head)
{
ListElem* temp;
ListElem* elem = head->next();
ListElem* prev = head;
head->next(0);
while(temp = elem->next())
{
elem->next(prev);
prev = elem;
elem = temp;
}
elem->next(prev);
head = elem;
}
在哪里
class ListElem{
public:
ListElem(int val): _val(val){}
ListElem *next() const { return _next; }
void next(ListElem *elem) { _next = elem; }
void val(int val){ _val = val; }
int val() const { return _val;}
private:
ListElem *_next;
int _val;
};
我正在使用 java 来实现这一点，并且方法是测试驱动开发，因此还附加了测试用例。
代表单个节点的 Node 类 -
package com.adnan.linkedlist;
/**
* User : Adnan
* Email : sendtoadnan@gmail.com
* Date : 9/21/13
* Time : 12:02 PM
*/
public class Node {
public Node(int value, Node node){
this.value = value;
this.node = node;
}
private int value;
private Node node;
public int getValue() {
return value;
}
public Node getNode() {
return node;
}
public void setNode(Node node){
this.node = node;
}
}
将起始节点作为输入并在不使用额外空间的情况下保留它的服务类。
package com.adnan.linkedlist;
/**
* User : Adnan
* Email : sendtoadnan@gmail.com
* Date : 9/21/13
* Time : 11:54 AM
*/
public class SinglyLinkedListReversal {
private static final SinglyLinkedListReversal service
= new SinglyLinkedListReversal();
public static SinglyLinkedListReversal getService(){
return service;
}
public Node reverse(Node start){
if (hasOnlyNodeInLinkedList(start)){
return start;
}
Node firstNode, secondNode, thirdNode;
firstNode = start;
secondNode = firstNode.getNode();
while (secondNode != null ){
thirdNode = secondNode.getNode();
secondNode.setNode(firstNode);
firstNode = secondNode;
secondNode = thirdNode;
}
start.setNode(null);
return firstNode;
}
private boolean hasOnlyNodeInLinkedList(Node start) {
return start.getNode() == null;
}
}
以及涵盖上述场景的测试用例。请注意，您需要junit jars。我正在使用 testng.jar；你可以使用任何你喜欢的东西..
package com.adnan.linkedlist;
import org.testng.annotations.Test;
import static org.testng.AssertJUnit.assertTrue;
/**
* User : Adnan
* Email : sendtoadnan@gmail.com
* Date : 9/21/13
* Time : 12:11 PM
*/
public class SinglyLinkedListReversalTest {
private SinglyLinkedListReversal reversalService =
SinglyLinkedListReversal.getService();
@Test
public void test_reverseSingleElement() throws Exception {
Node node = new Node(1, null);
reversalService.reverse(node);
assertTrue(node.getNode() == null);
assertTrue(node.getValue() == 1);
}
//original - Node1(1) -> Node2(2) -> Node3(3)
//reverse - Node3(3) -> Node2(2) -> Node1(1)
@Test
public void test_reverseThreeElement() throws Exception {
Node node3 = new Node(3, null);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 3; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
@Test
public void test_reverseFourElement() throws Exception {
Node node4 = new Node(4, null);
Node node3 = new Node(3, node4);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 4; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
@Test
public void test_reverse10Element() throws Exception {
Node node10 = new Node(10, null);
Node node9 = new Node(9, node10);
Node node8 = new Node(8, node9);
Node node7 = new Node(7, node8);
Node node6 = new Node(6, node7);
Node node5 = new Node(5, node6);
Node node4 = new Node(4, node5);
Node node3 = new Node(3, node4);
Node node2 = new Node(2, node3);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 10; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
@Test
public void test_reverseTwoElement() throws Exception {
Node node2 = new Node(2, null);
Node start = new Node(1, node2);
start = reversalService.reverse(start);
Node test = start;
for (int i = 2; i >=1 ; i -- ){
assertTrue(test.getValue() == i);
test = test.getNode();
}
}
}
作为替代方案，您可以使用递归-
struct node* reverseList(struct node *head)
{
if(head == NULL) return NULL;
if(head->next == NULL) return head;
struct node* second = head->next;
head->next = NULL;
struct node* remaining = reverseList(second);
second->next = head;
return remaining;
}
如果您使用链表作为堆栈结构，一个简单的算法：
#include <stdio.h>
#include <stdlib.h>
typedef struct list {
int key;
char value;
struct list* next;
} list;
void print(list*);
void add(list**, int, char);
void reverse(list**);
void deleteList(list*);
int main(void) {
list* head = NULL;
int i=0;
while ( i++ < 26 ) add(&head, i, i+'a');
printf("Before reverse: \n");
print(head);
printf("After reverse: \n");
reverse(&head);
print(head);
deleteList(head);
}
void deleteList(list* l) {
list* t = l;
while ( t != NULL ) {
list* tmp = t;
t = t->next;
free(tmp);
}
}
void print(list* l) {
list* t = l;
while ( t != NULL) {
printf("%d:%c\n", t->key, t->value);
t = t->next;
}
}
void reverse(list** head) {
list* tmp = *head;
list* reversed = NULL;
while ( tmp != NULL ) {
add(&reversed, tmp->key, tmp->value);
tmp = tmp->next;
}
deleteList(*head);
*head = reversed;
}
void add(list** head, int k, char v) {
list* t = calloc(1, sizeof(list));
t->key = k; t->value = v;
t->next = *head;
*head = t;
}
由于对 add 和 malloc 的附加函数调用可能会影响性能，因此地址交换的算法更好，但实际上会创建新列表，因此如果您将回调函数作为参数添加到逆转。
这是 C++11 中一种略有不同但简单的方法：
#include <iostream>
struct Node{
Node(): next(NULL){}
Node *next;
std::string data;
};
void printlist(Node* l){
while(l){
std::cout<<l->data<<std::endl;
l = l->next;
}
std::cout<<"----"<<std::endl;
}
void reverse(Node*& l)
{
Node* prev = NULL;
while(l){
auto next = l->next;
l->next = prev;
prev=l;
l=next;
}
l = prev;
}
int main() {
Node s,t,u,v;
s.data = "1";
t.data = "2";
u.data = "3";
v.data = "4";
s.next = &t;
t.next = &u;
u.next = &v;
Node* ptr = &s;
printlist(ptr);
reverse(ptr);
printlist(ptr);
return 0;
}
在这里输出
以下是使用 2 个指针（head 和 r）的一种实现
ListNode * reverse(ListNode* head) {
ListNode *r = NULL;
if(head) {
r = head->next;
head->next = NULL;
}
while(r) {
head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r->next));
r->next = reinterpret_cast<ListNode*>(size_t(r->next) ^ size_t(head));
head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r->next));
head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r));
r = reinterpret_cast<ListNode*>(size_t(r) ^ size_t(head));
head = reinterpret_cast<ListNode*>(size_t(head) ^ size_t(r));
}
return head;
}
curr = head;
prev = NULL;
while (curr != NULL) {
next = curr->next; // store current's next, since it will be overwritten
curr->next = prev;
prev = curr;
curr = next;
}
head = prev; // update head
class Node {
Node next;
int data;
Node(int item) {
data = item;
next = null;
}
}
public class LinkedList {
static Node head;
//Print LinkedList
public static void printList(Node node){
while(node!=null){
System.out.print(node.data+" ");
node = node.next;
}
System.out.println();
}
//Reverse the LinkedList Utility
public static Node reverse(Node node){
Node new_node = null;
while(node!=null){
Node next = node.next;
node.next = new_node;
new_node = node;
node = next;
}
return new_node;
}
public static void main(String[] args) {
//Creating LinkedList
LinkedList.head = new Node(1);
LinkedList.head.next = new Node(2);
LinkedList.head.next.next = new Node(3);
LinkedList.head.next.next.next = new Node(4);
LinkedList.printList(LinkedList.head);
Node node = LinkedList.reverse(LinkedList.head);
LinkedList.printList(node);
}
}
您只需使用一个 Extra 指针即可简单地反转链接列表。做到这一点的关键是使用递归。
这是Java程序。
public class Node {
public int data;
public Node next;
}
public Node reverseLinkedListRecursion(Node p) {
if (p.next == null) {
head = p;
q = p;
return q;
} else {
reverseLinkedListRecursion(p.next);
p.next = null;
q.next = p;
q = p;
return head;
}
}
// call this function from your main method.
reverseLinkedListRecursion(head);
如您所见，这是一个头递归的简单示例。我们主要有两种不同的递归。
在这里，程序将继续递归调用自身，直到我们的指针“p”到达最后一个节点，然后在返回堆栈帧之前，我们将头指向最后一个节点，额外的指针“q”反向构建链表.
在这里，堆栈帧将继续返回，直到堆栈为空。
这是python中的一个更简单的版本。它确实只使用两个指针slow&fast
def reverseList(head: ListNode) -> ListNode:
slow = None
fast = head
while fast:
node_next = fast.next
fast.next = slow
slow = fast
fast = node_next
return slow
只需交换第一个和最后一个（头和尾）指针即可使用XOR 链表，它在恒定时间内“自然可逆”。
void reverse() noexcept { std::swap(first_, last_); }
使用 1 个变量（仅p）的解决方案：
typedef unsigned long AddressType;
#define A (*( AddressType* )&p )
#define B (*( AddressType* )&first->link->link )
#define C (*( AddressType* )&first->link )
/* Reversing linked list */
p = first;
while( first->link )
{
A = A + B + C;
B = A - B - C;
A = A - B;
C = A - C;
A = A - C;
}
first = p;
您可以采用递归方法：
这是伪代码：
Node* reverse(Node* root)
{
if(!root) return NULL;
if(!(root->next)) temp = root;
else
{
reverse(root->next);
root->next->next = root;
root->next = NULL;
}
return temp;
}
调用该函数后，它返回temp链表的新根[]。很明显，它只使用了两个指针。
//with this no extra space and no extra scans but this code is reversing code but read
// in reverse direction no changes made in the linked list
PrintInReverse(Node node)
{
// given list is null
if(node ==null)
return null;
// if list contains only one node
if(node->next ==null)
{
print(node.value)
}
// call recursively
else
{
//while(node->next != null)// due to while loop it goes into infinite loop.use //if
if(node->next!=NULL)
{
PrintInReverse(node->next)
print(node.value)
}
}
}
Add comments...