Leetcode206-反转链表

反转链表

Leetcode209

题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路

头插法

直接以当前头节点来创建一个新链表，从head->next遍历，头插法插入新链表中。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

    ListNode* reverseList(ListNode* head) {
        if(head == nullptr)
            return head;
        ListNode* cur = head->next;
        ListNode* newHead = new ListNode(head->val);
        while(cur!=nullptr){
            ListNode* newNode = new ListNode(cur->val);
            newNode->next = newHead;
            newHead = newNode;
            cur = cur->next;
        }
        return newHead;
    }
};

双指针法

前面的头插法创建了一个新链表，内存开销较大，那能不能在原有基础上直接将next改变来逆转呢？答案是可以的，需要两个指针prev和cur，prev指向前一节点，cur指向后一节点，把后一节点cur的next指向前一节点prev即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:

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

### 递归法

原理同双指针法，只是用递归的方法做。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverse(ListNode* pre,ListNode* cur){
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
        return reverse(cur,temp);
    }

    ListNode* reverseList(ListNode* head) {
        return reverse(nullptr,head);
    }
};

参考

代码随想录