Wix网站开发 工作室西安百度公司官网

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)

第一想法：迭代，设置一个虚拟头结点，设定三个指针，prev，cur，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* 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;}
};