链表编程经验

如何保证不多,不漏,不越界

  • 首先保证不越界,如果在循环中需要有p->next->nextp->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;
    
}}

}

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 14:18
点赞 评论 收藏
分享
06-27 12:54
已编辑
门头沟学院 Java
累了,讲讲我的大学经历吧,目前在家待业。我是一个二本院校软件工程专业。最开始选专业是觉得计算机感兴趣,所以选择了他。本人学习计算机是从大二暑假结束开始的,也就是大三开始。当时每天学习,我个人认为Java以及是我生活的一部分了,就这样持续学习了一年半,来到了大四上学期末,大概是在12月中旬,我终于找的到了一家上海中厂的实习,但我发现实习生的工作很枯燥,公司分配的活也不多,大多时间也是自己在自学。就这样我秋招末才找到实习。时间来到了3月中旬,公司说我可以转正,但是转正工资只有7000,不过很稳定,不加班,双休,因为要回学校参加答辩了,同时当时也是心高气傲,认为可以找到更好的,所以放弃了转正机会,回学校准备论文。准备论文期间就也没有投递简历。然后时间来到了5月中旬,这时春招基本也结束了,然后我开始投递简历,期间只是约到了几家下场面试。工资也只有6-7k,到现在我不知道该怎么办了。已经没有当初学习的心劲了,好累呀,但是又不知道该干什么去。在家就是打游戏,boss简历投一投。每天日重一次。26秋招都说是针对26届的人,25怎么办。我好绝望。要不要参加考公、考研、央国企这些的。有没有大佬可以帮帮我。为什么感觉别人找工作都是顺其自然的事情,我感觉自己每一步都在艰难追赶。八股文背了又忘背了又忘,我每次都花很长时间去理解他,可是现在感觉八股、项目都忘完了。真的已经没有力气再去学习了。图片是我的简历,有没有大哥可以指正一下,或者说我应该走哪条路,有点不想在找工作了。
码客明:太累了就休息一下兄弟,人生不会完蛋的
如果实习可以转正,你会不...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务