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

思考题：

  • 请同时实现迭代版本和递归版本。

样例

1
2
3

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

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

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#define Node ListNode
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next == NULL) return head;
        //头插法
        //ListNode fake(-1);
        ListNode * p = NULL;
        
        while(true) {
            if(head==NULL) break;
            auto next= head->next;
            head->next = p;
            p = head;
            head = next;
            //head->next = 
            
        }
        
        return p;
        
        
    }
};