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

 


 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)