题目描述

Reverse a singly linked list.

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

题意：反转链表。以递归和迭代的方式分别实现。

算法1

迭代式

题解1:迭代式，使用两个辅助指针，pre指针记录当前节点的前驱节点，temp指针记录当前节点的后驱节点。做链表反转的时候，首先将$cur->next = pre,pre = cur,cur = temp$

    ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL)
        {
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;        
        }
        return pre;
    }

算法2

递归式

题解2:递归式。对于每一个链表节点，我们考虑先将其后续的链表进行反转。

1->2->3->4->5->NULL 假设我们已经将后面两个节点反转了得到了
1—>2->3->4<-5
    cur     p
那么我们执行cur->next->next = cur,cur->next = NULL可以得到
1—>2->3<-4<-5
递归进行即可

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

_