算法刷题-链表系列-两两交换链表结点、删除链表的倒数第n个元素

题目

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例：

要点 还是善用虚拟头结点注意循环结束条件，主要是，当一个结点类型的指针被赋给空值时，再取该结点->next会出现问题，所以要调整循环结束条件，和赋值的位置。 代码思路

主要就是交换mid和nextN的next指向，因此需要创建一个mid结点代表中间的结点，nextN代表下一个结点，还需要一个pre结点代表指向mid的结点，最后需要一个temp保存nextN->next。整体逻辑就是pre->mid->nextN。然后交换他们的next就好了。 当交换完毕，就变为pre->nextN->mid，此时pre=mid,mid=temp。注意next N的赋值，如果mid为空，是不能直接nextN=mid->next,报错。因此条件里要加上mid = null。判断完之后，再在循环一开始给nextN赋值。

代码 /** * 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) {} * }; */ #include <iostream> using namespace std; class Solution { public: ListNode* swapPairs(ListNode* head) { ListNode* pre; ListNode* mid; ListNode* nextN; ListNode* temp; ListNode* first = new ListNode(0); first -> next = head; pre = first; mid = head; //注意当循环到mid为空的时候，如果再使得 nextN=mid->next,空->空有问题，所以最好就先判断mid再下一步 //判断mid -> next是为了判断还剩一个的情况，这是不用交换直接退出 while (mid != nullptr && mid -> next != nullptr) { nextN = mid -> next; temp = nextN -> next; //下一次循环的mid mid -> next = nextN -> next; //if( mid == nullptr) cout << "333mid为空" << endl; nextN -> next = mid; pre -> next = nextN; pre = mid; mid = temp; } return first -> next; } }; 题目

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 示例：

要点

1.引入一个哨兵指针的思想，利用双指针，一个先走（哨兵）多少步用于观察前方情况，等到走到指定步数之后，指针1和2再同时往前走，直到指针1走到了链表尾部，那么指针2也到达了规定的地点。 这里之所以移动n+1个单位，是因为要删除的是倒数第n个结点，那么需要利用这个节点的前一个结点来删除嘛。

代码 双指针，哨兵 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* slow = dummyHead; ListNode* fast = dummyHead; while(n-- && fast != NULL) { fast = fast->next; } fast = fast->next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点 while (fast != NULL) { fast = fast->next; slow = slow->next; } slow->next = slow->next->next; // ListNode *tmp = slow->next; C++释放内存的逻辑 // slow->next = tmp->next; // delete tmp; return dummyHead->next; } }; 暴力法法法

就是先计算有多少个结点，然后走到结点数-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* first = new ListNode(0); first -> next = head; ListNode* cur = head; int count = 0; while (cur) { count++; cur = cur -> next; } cur = first; for (int i = 0; i != count-n; i++) { cur = cur -> next; } ListNode* temp = cur -> next; cur -> next = temp -> next; delete temp; return first -> next; } };