题目描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

样例

输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

C++ 代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
    /*  
        // 三指针
        ListNode* p1, *p2, *p3;
        if (head == NULL || head->next == NULL)
            return head;

        p1 = head;
        p2 = p1->next;
        while (p2) {
            p3 = p2->next;
            p2->next = p1;

            p1 = p2;
            p2 = p3;

        }

        head->next = NULL;
        head = p1;

        return head;
    */

        // 递归
        if (head == NULL || head->next == NULL) {
            return head;
        } else {

            ListNode* guard = head->next;
            ListNode* ret = reverseList(head->next);

            guard->next = head;
            head->next = NULL;

            return ret;
        }
    }
};