力扣 206. 反转链表

链接

思路

1、先引入一个数组，然后转置数组，再把数组赋值给链表

2、尾插法遍历旧链表，头插法建立新链表

代码1

/**
 * 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* l1 = head;
        vector <int> vec;
        while(l1){
            vec.push_back(l1->val);
            l1 = l1->next;
        }
        reverse(vec.begin(),vec.end());
        l1 = head;
        int i = 0;
        while(l1){
            l1->val = vec[i];
            l1 = l1->next;
            i++;
        }
        return head;
    }
};
           

代码2

/**
 * 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* l1;
        l1 = head;
        ListNode* l2=nullptr;
        if(l1){
            l2 = new ListNode;
            l2->val = l1->val;
            l1 = l1->next;
        }
        while(l1){
            ListNode* l3 = new ListNode;
            l3->val = l1->val;
            l3->next=l2;
            l2 = l3;
            l1= l1->next;
        }
        return l2;
    }
};
           

代码随想录方法

//双指针法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};