[0206.翻转链表]
/**
* 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 * pre = head;
ListNode * cur = head->next;
while(cur != NULL){
ListNode * tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
head->next = NULL;
return pre;
}
};
- 控制台给的例子运行没问题 但提交上去说是什么null。o 原来是我没考虑head是个空指针的情况
/**
* 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 == NULL)
return head;
ListNode * pre = head;
ListNode * cur = head->next;
while(cur != NULL){
ListNode * tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
head->next = NULL;
return pre;
}
};
- 用C++就是比较顺手啊，主要本科学C++语言学得比java扎实，数据结构课程和算法分析课程都是C++语言，用的顺手了。结合自身实际再加上客观环境我发现还是C++适合我啊，跟一开始想的方向一致，努力叭 :）
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;
}
};
- 还是随想录给的逻辑清楚 多看多写吧
[标准答案]
- 双指针法
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;
}
};
- 递归法
递归法相对抽象一些，但是其实和双指针法是一样的逻辑，同样是当cur为空的时候循环结束，不断将cur指向pre的过程。
关键是初始化的地方，可能有的同学会不理解， 可以看到双指针法中初始化 cur = head，pre = NULL，在递归法中可以从如下代码看出初始化的逻辑也是一样的，只不过写法变了。
具体可以看代码（已经详细注释），双指针法写出来之后，理解如下递归写法就不难了，代码逻辑都是一样的。
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和双指针法的代码进行对比，如下递归的写法，其实就是做了这两步
// pre = cur;
// cur = temp;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 和双指针法初始化是一样的逻辑
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};
我们可以发现，上面的递归写法和双指针法实质上都是从前往后翻转指针指向，其实还有另外一种与双指针法不同思路的递归写法：从后往前翻转指针指向。
具体代码如下（带详细注释）：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 边缘条件判断
if(head == NULL) return NULL;
if (head->next == NULL) return head;
// 递归调用，翻转第二个节点开始往后的链表
ListNode *last = reverseList(head->next);
// 翻转头节点与第二个节点的指向
head->next->next = head;
// 此时的 head 节点为尾节点，next 需要指向 NULL
head->next = NULL;
return last;
}
};
[0024.两两交换链表中的节点]
/**
* 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* swapPairs(ListNode* head) {
if (head == NULL || head->next == NULL){
return head;
}
ListNode* shead = new ListNode(0 , head);
ListNode* cur = shead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* temp1 = cur->next;
cur->next = cur->next->next;
ListNode* temp2 = cur->next->next->next;
cur->next->next->next = temp1;
temp1->next = temp2;
cur = temp1->next;
}
return head;
}
};
-
1.是中间变量设谁 不够清楚 2.是没有注意到 第二行按cur->next->next寻找时 其中要经过的cur->next已经改变了 不再是之前（第一行）那个cur->next路径了 也是就是说 按顺序执行代码时 上一行的赋值会影响下一条的赋值
cur->next = cur->next->next;cur->next->next = temp1;cur->next->next->next = temp2;
/**
* 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* swapPairs(ListNode* head) {
ListNode* shead = new ListNode(0 , head);
ListNode* cur = shead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* temp1 = cur->next;
ListNode* temp2 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp1;
cur->next->next->next = temp2;
cur = cur->next->next;
}
return head;
}
};
-
结果不对
输入 [1,2,3,4] 输出[1,4,3] 预期结果[2,1,4,3]
/**
* 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* swapPairs(ListNode* head) {
ListNode* shead = new ListNode(0 , head);
ListNode* cur = shead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* temp1 = cur->next;
ListNode* temp2 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp1;
cur->next->next->next = temp2;
cur = cur->next->next;
}
return shead->next;
}
};
- 原因是因为最后return语句 不应该再是返回head 因为经过两两交换后 head指向的是第链表中二个元素 而不是第一个
[标准答案]
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
ListNode* cur = dummyHead;
while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode* tmp = cur->next; // 记录临时节点
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
cur->next = cur->next->next; // 步骤一
cur->next->next = tmp; // 步骤二
cur->next->next->next = tmp1; // 步骤三
cur = cur->next->next; // cur移动两位，准备下一轮交换
}
return dummyHead->next;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)