单向链表反转链表_反转单个链表

Problem statement: Given a linked list reverse it without using any additional space (In O(1) space complexity).

问题陈述：给定的链表在不使用任何额外空间的情况下将其反向(O(1)空间复杂度)。

Solution:

解：

Reversing a single linked list is about reversing the linking direction. We can solve the above problem by following steps:

反转单个链表是关于反转链接方向。我们可以通过以下步骤解决上述问题：

1. Building the linked list

1.建立链表

Firstly, we build the linked list by inserting each node at the beginning. For detailed analysis of how to build a linked list using insertion at beginning, kindly go through this full article: Single linked list insertion

首先，我们通过在开头插入每个节点来构建链接列表。有关如何在一开始使用插入来构建链表的详细分析，请阅读全文： 单链表插入

2. Function to reverse the link list

2.反向链接列表功能

As told previously, the basic idea to reverse a linked list is to reverse the direction of linking. This concept can be implemented without using any additional space. We need three pointers *prev, *cur, *next to implement the function. These variables are named accordingly to indicate their serving part in the function.

如前所述，反向链接列表的基本思想是反向链接的方向。可以在不使用任何额外空间的情况下实现此概念。我们需要三个指针* prev ， * cur和* next来实现该功能。相应地命名这些变量以指示它们在函数中的服务部分。

*prev - to store the previous node which will become ultimately the next node after reversal for current node

* prev-存储前一个节点，该节点将在当前节点反转后最终成为下一个节点

*cur - to store the current node

* cur-存储当前节点

*next - to store the next node which will become current node in the next iteration.

* next-存储将在下一次迭代中成为当前节点的下一个节点。

Initialize *prev & *next to NULL, *cur to head

初始化* prev和* next为NULL， * cur为首

while(cur!=NULL)
    Set *nextto cur->next
    Set cur->nextto *prev
    Set *prev to *cur
    Set *cur to *next
End While loop
Set head to *prev

3. Print the reversed linked list

3.打印反向链接列表

Example:

例：

Let the linked list be 1->2->3->4->5->NULL
(for simplicity in understanding representing 
pointer to node by node value)
Head is 1
Initialize:
cur =1, prev=NULL, next=NULL

in iteration 1:
next=2
cur->next=NULL
prev=1
cur=2
thus reversed part: 1->NULL

in iteration 2:
next=3
cur->next=1
prev=2
cur=3
thus reversed part: 2->1->NULL

in iteration 3:
next=4
cur->next=2
prev=3
cur=4
thus reversed part: 3->2->1->NULL

in iteration 4:
next=5
cur->next=3
prev=4
cur=5
thus reversed part: 4->3->2->1->NULL

in iteration 5:
next=NULL
cur->next=4
prev=5
cur=NULL
thus reversed part: 5->4->3->2->1->NULL
iteration ends at cur is NULL
linked list reversed, head at 5

C ++程序反向链接单个链表 (C++ program to reverse a single linked list)

#include<bits/stdc++.h>

using namespace std;

class node{
	public:
		int data; // data field
		node *next;
};

node* reverse(node* head){
	node *next=NULL,*cur=head,*prev=NULL; //initialize the pointers
	while(cur!=NULL){//loop till the end of linked list
		next=cur->next;//next = cur->next to store the rest of the list;
		cur->next=prev;//change the direction of linked list
		prev=cur; //update prev
		cur=next; //update cur
	}

	head=prev; //update head
	return head; //return head
}

void traverse(node* head){
	node* current=head; // current node set to head
	int count=0; // to count total no of nodes
	printf("\ntraversing the list\n");
	while(current!=NULL){ //traverse until current node isn't NULL
		count++; //increase node count
		printf("%d ",current->data);
		current=current->next; // go to next node
	}
	printf("\ntotal no of nodes : %d\n",count);
}

node* creatnode(int d){
	node* temp=(node*)malloc(sizeof(node));
	temp->data=d;
	temp->next=NULL;
	return temp;
}

int main(){
	printf("creating the linked list by inserting new nodes at the begining\n");
	printf("enter 0 to stop building the list, else enter any integer\n");
	int k,count=1,x;

	node* curr;

	scanf("%d",&k);
	node* head=creatnode(k); //buliding list, first node
	scanf("%d",&k);

	//inserting at begining
	while(k){
		curr=creatnode(k);
		curr->next=head;   //inserting each new node at the begining
		head=curr;
		scanf("%d",&k);
	}
	traverse(head); // displaying the list

	cout<<"reversing the list............"<<endl;
	head=reverse(head);// reverse the linked list
	traverse(head);//display reversed linked list

	return 0;	
}

Output

输出量

creating the linked list by inserting new nodes at the begining 
enter 0 to stop building the list, else enter any integer 
6 
7 
8 
9 
4 
3 
3 
1 
0 

traversing the list 
1 3 3 4 9 8 7 6 
total no of nodes : 8 
reversing the list............

traversing the list 
6 7 8 9 4 3 3 1 
total no of nodes : 8