23.两两交换链表中的两个节点
题目链接 文章讲解 视频讲解
- 时间复杂度 o(n)
- 空间复杂度 o(1)
tips: 画图，并将每一步操作用伪代码写出来，然后将代码理顺可以避免修改代码的麻烦
初始化的时候就要将previous初始化为current的前一个节点，这样可以保证循环的第一步满足循环要求
class Solution {
public:ListNode* swapPairs(ListNode* head) {// 定义虚拟头节点ListNode * dummy = new ListNode();dummy->next = head;// 初始化current指向第一个节点也就是头节点，previous指向current的前一个节点ListNode * current = head, * previous = dummy;// 如果current不为空执行循环while(current) {// 定义一个节点保存带交换的两个节点的前一个节点ListNode * temp = previous;// previous指向带交换的两个节点中第一个节点previous = current;// 如果current的下一个节点不为空，那么current指向待交换的两个节点中第二个节点if(current->next) {current = current -> next;// 交换两个节点previous->next = current->next;current->next = previous;temp->next = current;} else {// 如果current的下一个节点为空那么只有一个待交换节点，此时返回return dummy->next;}// current指向下一组待交换的两个节点中的第一个节点current = previous->next;}return dummy->next;}
};
19.删除链表的倒数第N个节点
题目链接 文章讲解 视频讲解
tips: 这里再删除的时候不需要判断slow是否为空因为最开始的时候slow指向dummy,slow->next指向head，两者都不为空，在有fast作为先导的情况下，slow不可能为空,slow的next也不可能为空
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode * dummy = new ListNode;dummy->next = head;ListNode * fast = dummy;ListNode * slow = dummy;while(n-- && fast) fast = fast->next;while(fast->next) { // 慢指针出发fast = fast->next;slow = slow->next;}ListNode *temp = slow->next;slow->next = slow->next->next;delete temp;return dummy->next;}
};
面试题02.07链表相交
题目链接 文章链接
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * curr_a = headA, * curr_b = headB;while(curr_a != curr_b) {if(curr_a) {curr_a = curr_a->next;} else {curr_a = headB;}if(curr_b) {curr_b = curr_b->next;} else {curr_b = headA;}}return curr_a;}
};
