leetcode-反转链表

点击：题目链接：反转一个单链表。

思路

使用迭代的方式，我们可以创建一个尾节点，然后将链表依次改变顺序，最后返回尾节点。

需要注意的是，当我们改变链表前部节点的引用关系时，需要创建一个临时节点来保存它的后面节点

代码

/**
 * 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* tail = NULL;

        while(head){
            ListNode* temp = head->next;
            head->next = tail;
            tail = head;
            head = temp;
        }
        return tail;
    }
};

复杂度

时间:O(N) 空间:O(1)

思路

由于该解题也包含层层递进的关系在里面，我们也可以尝试使用递归的方式。和迭代的方式不同，递归是从尾部节点开始置换。
我们需要不断遍历到链表的尾部，然后开始不断层层反转尾部链表。

代码

class Solution {
public:
    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;
    }
};

复杂度

时间：O（N）， 空间：O(N)