反转链表 | CYY's Blog

题目来源

www.acwing.com/problem/content/33/

题目

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

思考题

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

样例

1
2
3

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

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

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* newHead = (ListNode*)malloc(sizeof(ListNode));
        newHead->next = NULL;
        
        ListNode* nowNode = head;
        ListNode* nextNode;
        while(nowNode){
            nextNode = nowNode->next;
            nowNode->next = newHead->next;
            newHead->next = nowNode;
            nowNode = nextNode;
        }
        return newHead->next;
        
    }
};