单链表的翻转
// 链表定义
struct SingleLinkedList {
int value;
struct SingleLinkedList *next;
};
// 打印链表中的数据
void printAllNodes(struct SingleLinkedList *head) {
printf("%d \t", head->value);
if (head->next == NULL) {
return;
}
printAllNodes(head->next);
}
// 翻转单向链表
struct SingleLinkedList * reverseLinkedList(struct SingleLinkedList *head) {
if (head == NULL) {
return head;
}
if (head->next == NULL) {
return head->next;
}
struct SingleLinkedList *preNode = NULL;
struct SingleLinkedList *nextNode = NULL;
while (head != NULL) {
// 1.把前面的一个节点给下一个
// 获取后继节点
nextNode = head->next;
// 新的后继节点指向前驱节点,实现翻转
head->next = preNode;
// 2.将当前节点向后移动
preNode = head;
head = nextNode;
}
return preNode;
}
测试
struct SingleLinkedList *linkedRoot = (struct SingleLinkedList *)malloc(sizeof(struct SingleLinkedList));
linkedRoot->value = 100;
linkedRoot->next = (struct SingleLinkedList *)malloc(sizeof(struct SingleLinkedList));
linkedRoot->next->value = 99;
linkedRoot->next->next = (struct SingleLinkedList *)malloc(sizeof(struct SingleLinkedList));
linkedRoot->next->next->value = 98;
linkedRoot->next->next->next = (struct SingleLinkedList *)malloc(sizeof(struct SingleLinkedList));
linkedRoot->next->next->next->value = 97;
printf("翻转前:\t");
printAllNodes(linkedRoot);
printf("\r\n翻转后:\t");
struct SingleLinkedList * reversedLinked = reverseLinkedList(linkedRoot);
printAllNodes(reversedLinked);