Created
October 17, 2016 12:30
-
-
Save tamarous/f4191278662ce494d9cc4e5ac090cd29 to your computer and use it in GitHub Desktop.
反转链表,链表带有头节点
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
struct Node; | |
typedef struct Node * ptrToNode; | |
typedef ptrToNode List,Position; | |
struct Node | |
{ | |
int element; | |
ptrToNode next; | |
}; | |
List makeList() | |
{ | |
ptrToNode head = (ptrToNode)malloc(sizeof(struct Node)),p = head; | |
int n,e; | |
head->next = NULL; | |
printf("Please enter the number of elements in this list: "); | |
scanf("%d",&n); | |
for(int i = 0;i < n;i++) | |
{ | |
printf("Enter the %dth element: ",i+1); | |
scanf("%d",&e); | |
ptrToNode node = (ptrToNode)malloc(sizeof(struct Node)); | |
node->element = e; | |
node->next = NULL; | |
head->next = node; | |
head = head->next; | |
} | |
return p; | |
} | |
List reverse(List l) | |
{ | |
if (l == NULL && l->next == NULL) | |
return NULL; | |
ptrToNode head = l,next = NULL; | |
ptrToNode pre = NULL; | |
ptrToNode ptrToFirst = l->next; | |
while (head != NULL) | |
{ | |
next = head->next; | |
head->next = pre; | |
pre = head; | |
head = next; | |
} | |
ptrToNode newHead = (ptrToNode)malloc(sizeof(struct Node)); | |
newHead->next = pre; | |
ptrToFirst->next = NULL; | |
return newHead; | |
} | |
void printList(List l) | |
{ | |
Position p = l->next; | |
while (p != NULL) | |
{ | |
printf("%d ",p->element); | |
p = p->next; | |
} | |
printf("\n"); | |
} | |
int main() | |
{ | |
List l = makeList(); | |
printList(l); | |
List nl = reverse(l); | |
printList(nl); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
因为链表带有头节点,所以在反转后,需要再创建一个头节点,并将这个头节点的 next 指针指向原先的最后一个节点。