6-4 Reverse Linked List(20点)
1740 ワード
6-4 Reverse Linked List(20点)
Write a nonrecursive procedure to reverse a singly linked list in O(N) time using constant extra space.
Format of functions:
where
The function
Sample program of judge:
Sample Input:
Sample Output:
List Reverse(List L){
if (L->Next == NULL || L->Next->Next==NULL)
return L;
else {
PtrToNode p = L->Next;
PtrToNode q = p->Next;
if (q->Next == NULL) {
p->Next = NULL;
q->Next = p;
}
else{
PtrToNode tmp = q->Next;
p->Next = NULL;
while (tmp) {
q->Next = p;
p = q;
q = tmp;
tmp = tmp->Next;
}
q->Next = p;
}
L->Next = q;
}
return L;
}
Write a nonrecursive procedure to reverse a singly linked list in O(N) time using constant extra space.
Format of functions:
List Reverse( List L );
where
List
is defined as the following: typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node {
ElementType Element;
Position Next;
};
The function
Reverse
is supposed to return the reverse linked list of L
, with a dummy header. Sample program of judge:
#include
#include
typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
struct Node {
ElementType Element;
Position Next;
};
List Read(); /* details omitted */
void Print( List L ); /* details omitted */
List Reverse( List L );
int main()
{
List L1, L2;
L1 = Read();
L2 = Reverse(L1);
Print(L1);
Print(L2);
return 0;
}
/* Your function will be put here */
Sample Input:
5
1 3 4 5 2
Sample Output:
2 5 4 3 1
2 5 4 3 1
List Reverse(List L){
if (L->Next == NULL || L->Next->Next==NULL)
return L;
else {
PtrToNode p = L->Next;
PtrToNode q = p->Next;
if (q->Next == NULL) {
p->Next = NULL;
q->Next = p;
}
else{
PtrToNode tmp = q->Next;
p->Next = NULL;
while (tmp) {
q->Next = p;
p = q;
q = tmp;
tmp = tmp->Next;
}
q->Next = p;
}
L->Next = q;
}
return L;
}