在给定值之后反转链表,而不创建新节点
Reverse a linked list after a given value, without creating new nodes
我真的坚持这个练习。我可以毫无问题地反转链表,但我不知道如何在不创建新节点的情况下做到这一点。
实现函数reverse()来反转链表中的元素
从给定值的第一次出现开始。
例如给定输入 A B C D E F 和值 D return 列表 A B C F E D
您应该在不创建新节点的情况下就地执行此操作。
struct Node
{
struct Node* next;
int val;
};
void reverse( struct Node* head, int val);
你能给我一些提示吗?
这就是我现在拥有的:
struct Node
{
struct Node* next;
int val;
};
void reverse(struct Node* head)
{
struct Node *p = head,
*q = NULL,
*r;
while (p != NULL)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
q = head;
}
void reverseAfter( struct Node* head, int val )
{
while(head)
{
if(head->val == val)
reverse(head);
else
head = head->next;
}
}
像你这样一个简单的单链表可以看成一个栈。反转堆栈非常简单:从当前堆栈中弹出第一个节点,推入一个新堆栈。一次又一次,直到第一个堆栈为空。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int val;
struct Node *next;
} Node;
void reverse(Node **head){
Node *tmp, *list, *newList = NULL;
if (head==NULL || *head == NULL) return;
list = *head;
while(list != NULL){
tmp = list;
list = list->next;
tmp->next = newList;
newList = tmp;
}
*head = newList;
}
void print(Node *head){
while(head){
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
void reverseAfter(Node *head, int val){
//The first element excluded
if(head == NULL) return ;
while(head->next && head->next->val != val)
head = head->next;
reverse(&head->next);
}
int main(void){
Node *head;
Node n[6] = {
{1,NULL}, {2, NULL}, {3, NULL},
{4,NULL}, {5, NULL}, {6, NULL}
};
n[0].next = &n[1];n[1].next = &n[2];n[2].next = &n[3];
n[3].next = &n[4];n[4].next = &n[5];
head = &n[0];
print(head);//1 2 3 4 5 6
//reverse(&head);
reverseAfter(head, 4);
print(head);//1 2 3 6 5 4
return 0;
}
我真的坚持这个练习。我可以毫无问题地反转链表,但我不知道如何在不创建新节点的情况下做到这一点。
实现函数reverse()来反转链表中的元素 从给定值的第一次出现开始。 例如给定输入 A B C D E F 和值 D return 列表 A B C F E D
您应该在不创建新节点的情况下就地执行此操作。
struct Node
{
struct Node* next;
int val;
};
void reverse( struct Node* head, int val);
你能给我一些提示吗?
这就是我现在拥有的:
struct Node
{
struct Node* next;
int val;
};
void reverse(struct Node* head)
{
struct Node *p = head,
*q = NULL,
*r;
while (p != NULL)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
q = head;
}
void reverseAfter( struct Node* head, int val )
{
while(head)
{
if(head->val == val)
reverse(head);
else
head = head->next;
}
}
像你这样一个简单的单链表可以看成一个栈。反转堆栈非常简单:从当前堆栈中弹出第一个节点,推入一个新堆栈。一次又一次,直到第一个堆栈为空。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int val;
struct Node *next;
} Node;
void reverse(Node **head){
Node *tmp, *list, *newList = NULL;
if (head==NULL || *head == NULL) return;
list = *head;
while(list != NULL){
tmp = list;
list = list->next;
tmp->next = newList;
newList = tmp;
}
*head = newList;
}
void print(Node *head){
while(head){
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
void reverseAfter(Node *head, int val){
//The first element excluded
if(head == NULL) return ;
while(head->next && head->next->val != val)
head = head->next;
reverse(&head->next);
}
int main(void){
Node *head;
Node n[6] = {
{1,NULL}, {2, NULL}, {3, NULL},
{4,NULL}, {5, NULL}, {6, NULL}
};
n[0].next = &n[1];n[1].next = &n[2];n[2].next = &n[3];
n[3].next = &n[4];n[4].next = &n[5];
head = &n[0];
print(head);//1 2 3 4 5 6
//reverse(&head);
reverseAfter(head, 4);
print(head);//1 2 3 6 5 4
return 0;
}