代码随想录算法训练营第四天：链表part02
24. 两两交换链表中的节点
leetcode链接:https://leetcode.cn/problems/swap-nodes-in-pairs/description/
题目描述：给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
核心思路：主要关注各指针的指向，绘图来解决。
点击查看代码
class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* cur = dummyhead;while(cur->next != nullptr && cur->next->next != nullptr){ListNode* tmp = cur->next;ListNode* tmp1 = tmp->next->next;cur->next = tmp->next;cur->next->next = tmp;tmp->next = tmp1;cur = tmp;}ListNode* result = dummyhead->next;delete dummyhead;dummyhead = nullptr;return result;}
};
19.删除链表的倒数第N个节点
leetcode链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
题目描述：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
核心思路：定义变量来存储需要遍历链表的长度或者双指针法。
第一种方法：
点击查看代码
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {int size = 0;ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* cur = dummyhead;while(cur->next != nullptr){cur = cur->next;size++;}int m = size - n;cur = dummyhead;while(m--){cur = cur->next;}ListNode* tmp = cur->next;cur->next = tmp->next;tmp = dummyhead->next;delete dummyhead;return tmp;}
};
双指针法：双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
点击查看代码
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyhead = new ListNode(0);dummyhead->next = head;ListNode* fast = dummyhead;ListNode* slow = dummyhead;while(n--){fast = fast->next;}while(fast->next != nullptr){fast = fast->next;slow = slow->next;}ListNode* tmp = slow->next;slow->next = tmp->next;delete tmp;return dummyhead->next;}
};
点击查看代码
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {int lenA = 0,lenB = 0;ListNode* ptrA = headA;ListNode* ptrB = headB;while(ptrA != NULL){//不是ptr->next，因为不是遍历而是统计长度。ptrA = ptrA->next;lenA++;}while(ptrB != NULL){ptrB = ptrB->next;lenB++;}ptrA = headA;ptrB = headB;if(lenB > lenA){swap(lenA,lenB);swap(ptrA,ptrB);}int n = lenA - lenB;while(n--){ptrA = ptrA->next;}while(ptrA != NULL){if(ptrA == ptrB){return ptrA;}ptrA = ptrA->next;ptrB = ptrB->next;}return NULL;}
};
142.环形链表II
leetcode链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
题目描述：给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
核心思路：双指针遍历是否是环，根据数学推导，头节点到入口点的距离等于相遇点到入口点的距离，设置两个索引（头节点与相遇点各一个）指针来向下遍历，相遇点即是环的入口点。
点击查看代码
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while(fast != NULL && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if(fast == slow){ListNode* index1 = head;ListNode* index2 = fast;while(index1 != index2){index1 = index1->next;index2 = index2->next;}return index1;}}return NULL;}
};
相关新闻
