write a nonrecursive procedure to reverse a singly linked list in o(n) time using constant extra space.
时间: 2023-04-25 08:04:25 浏览: 95
使用常数额外空间,在O(n)时间内编写一个非递归程序来反转一个单向链表。
可以使用三个指针:prev,curr和next。prev指向当前节点的前一个节点,curr指向当前节点,next指向当前节点的下一个节点。在遍历链表时,将curr的next指向prev,然后将prev和curr向前移动一个节点,直到curr到达链表末尾。最后,将链表的头节点指向prev,即可完成反转。
相关问题
Write a program to reverse a string without using theandfunctions defined in the string.h library.
Sure, here's a program written in C to reverse a string without using any predefined functions from string.h library:
```
#include<stdio.h>
void reverseString(char str[]);
int main()
{
char str[100];
printf("Enter a string: ");
scanf("%s", str);
reverseString(str);
printf("Reversed string is: %s", str);
return 0;
}
void reverseString(char str[])
{
int length = 0;
// Calculate the length of the string
while (str[length] != '\0')
{
length++;
}
// Swap characters from beginning and end
for (int i = 0; i < length / 2; i++)
{
char temp = str[i];
str[i] = str[length - i - 1];
str[length - i - 1] = temp;
}
}
```
In this program, we first take input from the user and pass it to the `reverseString()` function. Inside this function, we calculate the length of the string by iterating through it till we find the null character `'\0'`. Then, we swap the first character with the last one, second with second last one, and so on till we reach the middle of the string. Finally, we print the reversed string.
A function that receives a LIST as an argument and returns the LIST in reverse.
As an AI language model, I don't have the capability to write code in a specific programming language. However, I can provide you with the general algorithm for reversing a list:
1. Create an empty list to store the reversed elements.
2. Iterate through the original list in reverse order, starting from the last element.
3. Append each element to the new list.
4. Return the new list.
Here's an example implementation in Python:
```
def reverse_list(lst):
reversed_lst = []
for i in range(len(lst)-1, -1, -1):
reversed_lst.append(lst[i])
return reversed_lst
```
This function takes a list `lst` as an argument and returns a new list with the elements in reversed order. The `range()` function is used to iterate through the original list in reverse order, starting from the last index (`len(lst)-1`) and ending at the first index (`-1`) with a step of `-1`. The `append()` method is used to add each element to the new list. Finally, the reversed list is returned.