链表常见题型(1)

发布时间:2023年12月20日

1.反转链表

1.1反转链表

? ? ? 如果我们想要反转链表,那应该有head的next指针指向空,其余结点的next指针反过来,指向它的上一个结点,那我们在执行该操作的时候就需要定义变量cur(current)表示我们当前遍历到的结点,变量pre(previous)表示上一个结点,对于第一个结点来说,它的上一个结点为空,我们需要把当前的next指针指向上一个结点,但两个变量够吗?当我们修改当前结点的next指针时,它的下一个结点就丢失了,所以在修改之前还需要再定义一个变量nxt(next)记录cur的下一个结点,之后我们就可以把cur的next指针指向pre,pre=cur,cur=nxt,如此循环,当反转结束后,pre指向反转这一段的末尾,cur指向反转这一段末尾的下一个结点,所以反转结束时,cur指向NULL,如图所示

 ListNode* reverseList(ListNode* head){
      ListNode* nxt;
      ListNode* pre=NULL;
      ListNode* cur=head;
      while(cur){
          nxt=cur->next;
          cur->next=pre;
          pre=cur;
          cur=nxt;
      }
      return pre;
    }

?1.2反转链表||

? ? ?做这道题我们要用到上一道题的性质:当反转结束后,pre指向反转这一段的末尾,cur指向反转这一段末尾的下一个结点。所以当翻转结束后cur指向5,pre指向4,所以我们要把2指向cur,1指向pre,这样就组成了14325,我们需要记录反转这一段的上一个结点p,所以就是把p的next指向cur,p指向pre,但是当left等于1时是没有p的,所以此时我们要建立一个虚拟头结点,代码如下

ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummyhead=new ListNode(0,head);
        ListNode* p=dummyhead;
         for (int i = 0; i < left - 1; ++i)
            p = p->next;

        ListNode *pre = NULL, *cur = p->next;
        for (int i = 0; i < right - left + 1; ++i) {
            ListNode *nxt = cur->next;
            cur->next = pre; 
            pre = cur;
            cur = nxt;
        }
        p->next->next = cur;
        p->next = pre;
        return dummyhead->next;
    }

1.3K个一组翻转链表

? ? ? 这个要求我们k个结点一组进行翻转,所以我们要先求出来链表的长度,如果大于等于k时,我们要判断剩余结点的个数,小于k是无法翻转的,翻转的过程和上一题是一样的,需要注意的是我们额外要在翻转之后把p更新成下一段要翻转的链表的上一个结点,但是由于最后我们修改了p的next指针,所以我们需要在修改之前额外创建一个临时变量nxt=p->next,翻转结束后令p=nxt开始下一段循环,不断循环,最后返回dummyhead->next,代码如下:

 ListNode* reverseKGroup(ListNode* head, int k) {
         ListNode* head1=head;
         int len=0;
         while(head1)
         {
             len++;
             head1=head1->next;
         }
        ListNode* dummyhead=new ListNode(0,head);
        ListNode* p=dummyhead;
        ListNode *pre = NULL, *cur = p->next;
        for (; len>=k;len-=k ) {
            for(int i=0;i<k;i++){
            ListNode *nxt = cur->next;
            cur->next = pre; 
            pre = cur;
            cur = nxt;
            }
        
        ListNode* nxt=p->next;
        p->next->next = cur;
        p->next = pre;
        p=nxt;
}
        return dummyhead->next;
    }

2.链表删除

? ? 我们要想删除链表的某个结点,需要利用上一个结点的next指针指向删除结点的下一个结点

2.1删除链表中的节点

?

? ? ?之前我们在基础数据结构讲过如何删除一个结点,但这个它不给我头结点,我怎么删除啊,这题就很秒,它说node不是链表的最后一个结点,也就是说我们可以把node结点的下一个结点的值复制过来,然后删除下一个结点,这可太妙了!

void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
}

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

? ? ?第一种做法就是遍历求出链表长度,这样我们就知道要删除的倒数第N个结点是正数的第几个了,我们再遍历到这个结点的上一个结点执行删除操作,同时因为n可能等于链表长度,所以我们需要建立虚拟头结点,这样就OK了。

? ? 第二种做法是快慢指针,我们需要找到倒数第N+1个结点,初始化右指针指向虚拟头结点,先让右指针走N步,然后初始化左指针指向虚拟头结点,左右指针一起向右移动,这样两个指针的距离始终为N,当右指针走向倒数第一个结点,左指针就恰好走到了倒数第N+1个结点,这时候就可以执行删除操作了!

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;
        }
        
        while(fast->next!=NULL){
            slow=slow->next;
            fast=fast->next;
        }
        slow->next=slow->next->next;
        return dummyhead->next;
    }

2.3删除排序链表中的重复元素

? ? ?这个题还是比较简单的,首先并不需要虚拟头结点,因为就算头结点的值和下一个结点的值相等,也会保留头结点,我们只需要遍历链表,如果cur的下一个结点的val值和cur的val值相等,我们就删除cur的下一个结点,需要注意的是循环条件是cur->next,当cur遍历到最后一个结点时,cur的下一个结点就不存在是NULL,此时应该退出循环,如果是cur则会继续进入循环造成NULL指针的解引用,会报错

    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL)return NULL;
        ListNode* cur=head;
        while(cur->next)
        {
            if(cur->next->val==cur->val)
            {
                cur->next=cur->next->next;
            }
            else
            {
            cur=cur->next;
            }
        }
        return head;
    }

?2.4 删除排序链表中的重复元素||

? ? ?首先这个题需要建立虚拟头结点,因为如果开头就有几个重复的结点,那么头结点会被删除,所以我们先创建一个虚拟头结点,然后初始化cur指针指向虚拟头结点,然后遍历链表,每次遍历时,先取出cur的next的值val,如果cur的next的next的值和val相等,再进入循环判断cur的next的值是否等于val,相等就删除,否则移动到下一个结点,最后返回头结点

 ListNode* deleteDuplicates(ListNode* head) {
         ListNode* dummyhead=new ListNode(0);
         dummyhead->next=head;
         ListNode* cur=dummyhead;
         while(cur->next&&cur->next->next)
         {
            int val=cur->next->val;
            if(cur->next->next->val==val)
            {
                while(cur->next&&cur->next->val==val)
                {
                    cur->next=cur->next->next;
                }
            }
            else
            {
                cur=cur->next;
            }
         }
         return dummyhead->next;
    }

?

文章来源:https://blog.csdn.net/pancodearea/article/details/135097362
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。