春季每日一题(3.17)反转链表

35. 反转链表

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

思考题：

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

样例

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

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

题解

/**
 * 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* prev = nullptr;
        ListNode* p = head;//当前位置
        while(p){
            ListNode* next = p->next;
            p->next = prev;
            prev = p;
            p = next;
        }
        return prev;
    }
};
           

• 思路就是，先存下当前位置后面的，然后把当前位置的下一位指向prev前面位置，然后prev往后移到当前位置，p移到之前存的next位置