劍指offer之反轉(zhuǎn)鏈表

1 問題

反轉(zhuǎn)鏈表，比如0->1->2->3反轉(zhuǎn)后變成了3->2->1->0

 
2 分析

搞3個(gè)指針，初始化一個(gè)指針，讓頭結(jié)點(diǎn)指向這里，然后另外一個(gè)指針初始化為NULL，然后讓第一個(gè)節(jié)點(diǎn)指向這里，然后頭結(jié)點(diǎn)依次向右移，這個(gè)初始化為NULL的指針也向右移動(dòng)，然后最后當(dāng)頭結(jié)點(diǎn)的next指向NULL的時(shí)候，我們直接返回這個(gè)節(jié)點(diǎn)就行了。

 
3 代碼實(shí)現(xiàn)

    #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 運(yùn)行結(jié)果

    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
深信服三年半工作經(jīng)驗(yàn)，目前就職游戲廠商，希望能和大家交流和學(xué)習(xí),
微信公眾號(hào)：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進(jìn)階人工智能(鏈接)