剑指offer之反转链表
1 问题
反转链表,比如0->1->2->3反转后变成了3->2->1->0
2 分析
搞3个指针,初始化一个指针,让头结点指向这里,然后另外一个指针初始化为NULL,然后让第一个节点指向这里,然后头结点依次向右移,这个初始化为NULL的指针也向右移动,然后最后当头结点的next指向NULL的时候,我们直接返回这个节点就行了。
3 代码实现
#include <stdio.h>
typedef struct Node
{
int val;
struct Node *next;
} Node;
/*
*print list
*/
void print_list(Node *head)
{
if (head == NULL)
{
printf("head is NULL\n");
return;
}
Node *p = head;
while (p != NULL)
{
printf("value is %d\n", p->val);
p = p->next;
}
}
/*
*reverse list
*/
struct Node* reverse(Node *head)
{
if (head == NULL)
{
printf("reverse head is NULL\n");
return NULL;
}
Node *end = NULL;
Node *p = head;
Node *start = NULL;
while (p != NULL)
{
//next node
Node *next = p->next;
//If next is NULL, we will store p, we will return p in the end;
if (next == NULL)
{
end = p;
}
p->next = start;
start = p;
p = next;
}
return end;
}
int main()
{
//0->1->2->3;
Node head, node1, node2, node3;
head.val = 0;
head.next = &node1;
node1.val = 1;
node1.next = &node2;
node2.val = 2;
node2.next = &node3;
node3.val = 3;
node3.next = NULL;
print_list(&head);
printf("list will reverse\n");
Node *hello = reverse(&head);
print_list(hello);
return 0;
}
4 运行结果
value is 0
value is 1
value is 2
value is 3
list will reverse
value is 3
value is 2
value is 1
value is 0
赞 (0)