安徽网站建设开发电话,云浮头条新闻,比较好看的wordpress主题,网站怎么升级day04打卡
面试题 02.07. 链表相交
时间复杂度#xff1a;O(N)#xff0c;空间复杂度#xff1a;O(1)
第一想法#xff1a;求出两个链表长度#xff0c;走差距步#xff0c;再遍历找有没有相交
/*** Definition for singly-linked list.* struct ListNode {* int…day04打卡
面试题 02.07. 链表相交
时间复杂度O(N)空间复杂度O(1)
第一想法求出两个链表长度走差距步再遍历找有没有相交
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* a headA, * b headB;//求出 两个链表的长度int lenA 0, lenB 0;while(a ! NULL) {lenA;a a-next;}while(b ! NULL){lenB;b b-next;}a headA, b headB;//让两个链表长度统一//让a做长的链表if(lenA lenB){swap(lenA, lenB);swap(a, b);}int n lenA - lenB;//a走差距步while(n--){a a-next;}//遍历链表看看有没有相交while(a ! NULL){if(a b) return a;else {a a-next;b b-next;}}return NULL;}
};19. 删除链表的倒数第 N 个结点
时间复杂度O(N)空间复杂度O(1)
第一想法双指针快指针先走n步再同时走走到快指针到空时修改慢指针的连接即可
/*** 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* removeNthFromEnd(ListNode* head, int n) {ListNode* newHead new ListNode;newHead-next head;ListNode* fast head, * slow newHead;//快指针先走n步while(n--) fast fast-next;//同时走快指针到空时slow就是倒数第n个节点while(fast ! nullptr){fast fast-next;slow slow-next;}slow-next slow-next-next;ListNode* ret newHead-next;delete newHead;return ret;}
};24. 两两交换链表中的节点 - 力扣LeetCode
时间复杂度O(N)空间复杂度O(1)
第一想法迭代设置一个虚拟头结点设定三个指针prevcurnext。修改链表关系即可
困难没有把握好三个指针的连接关系
看了题解画图实现了三个指针的链接关系和递归解法
/*** 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 nullptr || head-next nullptr) return head;// ListNode* newHead new ListNode;// newHead-next head;// ListNode* prev newHead, * cur head, * next head-next;// while(cur ! nullptr next ! nullptr)// {// prev-next next;// cur-next next-next;// next-next cur;// //交换节点// prev cur;// cur cur-next;// if(cur) next cur-next;// }// return newHead-next;//递归//递归出口if(head nullptr || head-next nullptr) return head;//子问题ListNode* newHead swapPairs(head-next-next);ListNode* ret head-next;head-next newHead;ret-next head;return ret;}
};
