206. Reverse Linked List leetcode list

1. Reverse Linked List

   方法一、采用非遞歸的方法，頭插入法

ListNode* reverseList(ListNode* head) {
        if(NULL == head || NULL == head->next)
        {
            return head;
        }

        ListNode* p1 = head; //存儲逆轉的連結清單的表頭
        ListNode* p2 = p1->next;
        p1->next = NULL;

        ListNode* tmp; //存儲連結清單未逆轉的連結清單的表頭

        while(p2)
        {
            tmp = p2->next;
            p2->next = p1;
            p1 = p2; 
            p2 = tmp;
        }

        return p1;
    }
           

方法二、采用遞歸的方法

ListNode* reverseList(ListNode* head) {
        if(NULL == head || NULL == head->next)
        {
            return head;
        }

        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newHead;
}