剑指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