删除链表的倒数第 N 个结点

结点"/>

删除链表的倒数第 N 个结点

LeetCode 19. 删除链表的倒数第 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* dummy = new ListNode(-1);dummy->next = head;ListNode *p = dummy , *q = dummy;while(n--)  p = p->next;while(p->next){p = p->next;q = q->next;}q->next = q->next->next;return dummy->next;}
};

关键

• 创建一个虚拟节点dummy，指向head
• 采用双指针p,q
• p 比 q领先 n 个位置
• p 指向最后一个节点 时， q 指向 要删除节点 的直接前驱

leetcode 237. 删除链表中的节点

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:void deleteNode(ListNode* node) {node->val = node->next->val;node->next = node->next->next;}
};

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:void deleteNode(ListNode* node) {*node = *(node->next);}
};

leetcode 83. 删除排序链表中的重复元素

/*** 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* deleteDuplicates(ListNode* head) {if(! head)return head;ListNode* p = head;while(p->next){if(p->val == p->next->val)p->next = p->next->next;else p = p->next;}return head;}
};

leetcode 61. 旋转链表

/*** 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* rotateRight(ListNode* head, int k) {if(!head || !head->next || !k)return head;ListNode* p = head;int n = 1;while(p->next){p = p->next;n ++;}k %= n;if(!k) return head;ListNode* dummy = new ListNode(-1);dummy->next = head;p = dummy;ListNode* q = dummy;while(k--)  p = p->next;while(p->next){p = p->next;q = q->next;}dummy->next = q->next;p->next = head;q->next = NULL;return dummy->next;}
};

注意

• 后三条 修改指针语句 有bug
• 故须 在程序 前面 处理 特殊情况
  1 链表仅有一个节点时
2 k % n = 0 时
• 核心思想

1. 旋转k次，即将链表的 后k个节点 作为一个 整体 放在表头
2. 故使用双指针找到 后k个节点

/*** 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* rotateRight(ListNode* head, int k) {if(!head)return head;ListNode* p = head;int n = 1;while(p->next){p = p->next;n ++;}k %= n;ListNode* dummy = new ListNode(-1);dummy->next = head;p = dummy;ListNode* q = dummy;while(k--)  p = p->next;while(p->next){p = p->next;q = q->next;}p->next = head;head = q->next;q->next = NULL;return head;}
};

leetcode 24. 两两交换链表中的节点

/*** 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)return head;ListNode* dummy = new ListNode(-1);dummy->next = head;ListNode* p = dummy;ListNode* q = head;while(q && q->next){p->next = q->next;q->next = q->next->next;p->next->next = q;p = q;q = q->next;}return dummy->next;}
};

• 情况① ： 表为空，直接返回
• 情况② ： 表中元素数目为奇数，最后一个不做处理，故while循环条件时q和q的后继不为空
• 情况③ : 一般情况