如何保证不多,不漏,不越界
- 首先保证不越界,如果在循环中需要有
p->next->next
或p->next->val
,就必须要保证p->next
非空指针,以此类推,如果要访问p->next->next->next
就要保证p->next->next
非空指针。
- 并且不越界的情况还有可能是返回空指针,应该在代码的前部进行if判断。
- 再考虑不漏的情况,一般可能在头节点和终止节点出现漏的情况,头节点的情况通常可以添加虚拟头节点保证不漏,如果要保证尾部不漏,比较好的方式是在循环条件中保证遍历所有节点,并在循环中使用if语句判断是否越界,以及对尾部使用特殊的处理方案。
//JZ76删除重复部分
class Solution {
public ListNode deleteDuplication(ListNode pHead) {
ListNode dummy = new ListNode(-1);
ListNode tail = dummy;
while (pHead != null) {
// 进入循环时,确保了 pHead 不会与上一节点相同
if (pHead.next == null || pHead.next.val != pHead.val) {
tail.next = pHead;
tail = pHead;
}
// 如果 pHead 与下一节点相同,跳过相同节点(到达「连续相同一段」的最后一位)
while (pHead.next != null && pHead.val == pHead.next.val) pHead = pHead.next;
pHead = pHead.next;
}
tail.next = null;
return dummy.next;
}
}
- 最后是考虑不重的情况,重复的可能会出现在节点的中间部分。
什么时候应该给链表添加虚拟头节点
- 当原头节点本身可能被删除时需要添加虚拟头节点,如下删除节点的算法所示,由于可能删除原头节点,因此需要添加虚拟头节点以链接下后面的节点
ListNode* deleteNode(ListNode* head, int val) {
if(head==nullptr) return NULL;
ListNode *vHead = new ListNode(-1);
vHead->next = head;
ListNode *p = vHead;
while(p->next!=nullptr){
if(p->next->val==val){
p->next = p->next->next;
break;
}
p = p->next;
}
return vHead->next;
}
通用方法
1.双指针法
1.1 倍速双指针
//JZ23 寻找环的入口节点
ListNode* EntryNodeOfLoop(ListNode* pHead) {
ListNode *pFast = pHead;
ListNode *pSlow = pHead;
while (1){
pSlow = pSlow->next;
//pFast的速度是pSlow的两倍,要保证pFast不越界,因此既要保证pFast非空,又要保证pFast->next非空
if(pFast&&(pFast=pFast->next)){
pFast=pFast->next;
}
else{
return NULL;
}
if(pSlow==pFast) break;
}
pSlow = pHead;
while(pSlow!=pFast){
pSlow = pSlow->next;
pFast = pFast->next;
}
return pSlow;
}
1.2 等距双指针
//JZ22 获取倒数第k个节点
ListNode* FindKthToTail(ListNode* pHead, int k) {
ListNode *p1,*p2;
p1 = pHead;
p2 = pHead;
//首先考虑返回空指针的情况
if(k==0) return NULL;
if(!p1) return NULL;
//将快指针放到距离慢指针k-1个距离的地方,如果距离不够就返回空指针
for(int i=1;i<k;i++){
if(!(p1=p1->next)){
return NULL;
break;
}
}
while(p1->next){
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
1.3 条件双指针
//一种使用指针将元素后移的方法
void func(int* p, int n) {
int id=0;
int temp;
for(int i=0;i<n;i++){
if(p[i]!=0){
temp = p[i];
p[i] = p[id];
p[id++] = temp;
}}
}