删除链表的倒数第n个节点
遍历算出数目，再删除
#include <iostream> #include <vector> #include<algorithm> using namespace std; 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) { int length = 0; ListNode* temp1 = head , *temp2; while (temp1!=nullptr) { temp1 = temp1->next; length++; } if (n == length) { temp2 = head; head = head->next; delete temp2; } else { temp1 = head; for (int i = 0; i < length - n - 1; i++ ) { temp1 = temp1->next; } temp1->next = temp1->next->next; } return head; } }; int main() { vector<int> head = { 1,2 ,3,4 ,5}; ListNode* head_test = new ListNode(0); ListNode* test , *cur = head_test; Solution a; for (int i = 0; i < head.size(); i++) { ListNode* temp = new ListNode(head[i]); cur->next = temp; cur = cur->next; } cur->next = nullptr; cur = head_test; cout << "cur list" << endl; while (cur->next != nullptr) { cout << cur->val << ' '; cur = cur->next; } cout << cur->val << endl; test = a.removeNthFromEnd(head_test->next,2); while (test->next != nullptr) { cout << test->val << ' '; test = test->next; } cout << test->val << ' '; return 0; }
双指针法
快慢双指针，两个指针直接相隔n个
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *pre ,*aft ,*temp; ListNode* dunmy_head = new ListNode(0, nullptr); dunmy_head->next = head; pre = dunmy_head; aft = pre; for (int i = 0; i < n+1; i++) { aft = aft->next; } while (aft != nullptr) { pre = pre->next; aft = aft->next; } cout << pre->val << endl; temp = pre->next; pre->next = pre->next->next; delete temp; return dunmy_head->next; } };
双指针法 ，卡尔
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; return dummyHead->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* removeNthFromEnd(ListNode* head, int n) { if(head->next == nullptr && n==1) return nullptr; int num = 0; ListNode *cur = head; while(cur!=nullptr) { cur = cur->next; num++; } if(n == num ) return head->next; else { num = num - n - 1; cur = head; while(num--) cur = cur->next; ListNode *tmp = cur->next->next; cur->next = tmp; } return head; } };
