1.4~1.5链表复习,代码操作(反转链表(用栈解决,双指针),删除链表指定元素),链表选择题,广义表

发布时间:2024年01月08日

删除链表内指定范围的数

思路是双指针,定义两个指针,一个去找当前这个数满不满足要求,然后另一个定义为删除区间的起点 ,

当不满足时,两个指针同时向后移动;当满足时,前驱指针就不动了,不断的删掉当前的cur,直到为Nullptr或出了区间

node* del(int s, int e, node* head) {
    if (!head)return nullptr;
    node* pre = head, * cur = head->next;//pre表示区间起点,cur表示操作结点
    while (cur) {//只要不空就是还能操作
        if (cur->val <= s) {//当前的结点还不满足操作要求
            pre = cur;
            cur = cur->next;
        }//同时向后移动两个指针
        else {//满足一个要求
            if (cur->val < e) {//满足两个要求
                pre->next = cur->next;//删除掉当前的结点
                cur = cur->next;
            }
            else {
                break;
            }
        }
    }
}

反转链表

双指针

用一个指针,保存为当前遍历到的节点,再来一个指针为当前这个遍历到节点的前一个结点,

这个过程就相当于把链表拆成了两部分,一部分是已经反转好的链表,Pre为其头结点

另一部分为还未反转的原始链表,cur为其头结点,

算法的过程就是不断把未反转的链表的头结点转给反转的链表,让pre去接受

while(cur){//循环条件为,未反转的链表里还有元素,所以就是cur不为空,cur一旦为空就说明为反转的链表已经为空,就不用再反转了

node* temp=cur->next;//保存未反转链表的头结点

cur->next=pre;//把此时未反转链表的头结点接到反转链表上

pre=cur;//更新反转链表的头结点

cur=temp;//更新未反转链表的头结点

}

return pre;//最后返回反转链表的头结点pre

这个C不对,因为更新未排序链表以及已排序链表的顺序反了,应该先更新已倒序的,再更新未倒序的,否则就会导致下一个头结点直接被跳过?

用栈解决

由于栈可以先进先出,所以可以用栈去解决

import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
    Stack<ListNode> stack= new Stack<>();
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    //栈中的结点全部出栈,然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点,一定要让他的next
    //等于空,否则会构成环
    node.next = null;
    return dummy;
}
}

链表选择题

top指向栈的顶部,是空结点,然后让新插入的结点下一个指针指向它,

链栈的话,插入是要插入在头结点位置的,即TOP其实是相当于一个头结点的位置,往链栈里插元素,就是在往链表的第一个位置上放元素,所以是C的操作

就是说每个结点都会有两个链域,但是每个结点都会被一个链域唯一确定,除了根节点,所以一共2n个链域,有n-1是被用的,剩下n+1是没被用的

换个思路就是操场跑圈,相对速度为2,跑完一圈的步数为100/2=50?

A.单链表的没个节点都具有唯一的前驱节点和唯一的后继节点,所以当两个单链表存在相交的节点时,这两个链表则同时拥有这个节点,以及这个节点的所有后继节点,当这个公共节点是尾节点时,他们则只含有公共一个节点-------尾节点。 B.快慢指针是判断单链表是否有环的一种方法:两个指针,每次移动的步长为2叫做快指针,每次移动步长为1的指针叫做慢指针。快慢指针同时从头结点出发,当快指针率先到达NULL的时候,则说明此单链表中不存在环,当快指针追上慢指针的时候,说明此单链表中存在环。 C.有环的单向链表和无环的单向链表不能相交,因为当相交的时候,无环的单向链表也会被迫存在一个环,只不过这个环的”起点“可能不是原来单向链表的头结点。 4.两个单向链表之间相交可以存在环。?

两个。 一个每次走一步, 一次每次走两步, 会相遇就表示有环?

尾节点的后继指向头结点,而头结点不是尾节点的逻辑后继

注意是单链表而不是数组?

数组静态分配内存,链表动态分配内存; 数组在内存中连续,链表不连续; 数组元素在栈区,链表元素在堆区; 数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);?

数组对象是放在堆内存中,引用是放在栈内存中

考虑两个极端,最少是1,即头部,最坏是尾部,要N,中间是线性平均,所以为D?

在位置I上删除是N-I,即区间I到N,只含一个端点

在位置I上添加是N-I+1,区间两端点都要?

C除头结点外D考虑空表或只有一个元素

删除元素,删除元素的话需要知道前一个元素的指针;要在指定位置插入,就需要知道指定位置的指针,要删除的话,就是让删除位置的元素前一个元素的指针不再指向它,而是指向空指针或它后面的元素,越过他就行;插入的话就直接在指定位置接上要插入的元素即可

单链表与单循环链表b

b

只需要找到被接的链表的尾部,一个OM,然后接的链表,只要头结点即可?

队列

往队列的队尾插入一个元素为入队,从队列的排头删除一个元素称为退队。初始时?front=rear=0?,?front?总是指向队头元素的前一位置,入队一次?rear+1?,退队一次?front+1?。队列队头队尾指针相同时队列为空。而带链的队列,由于每个元素都包含一个指针域指向下一个元素,当带链队列为空时?front=rear=Null?,插入第?1?个元素时,?rear+1?指向该元素,?front+1?也指向该元素,插入第?2?个元素时?rear+1?,?front?不变,删除?1?个元素时?front+1?。即?front=rear?不为空时带链的队列中只有一个元素。故本题答案为?A?选项。?

奇怪的选择题

报错

这个需要注意,vector删除后,后续下标会自动往前走,而i++,所以就会导致4被空掉?

广义表

head返回第一个元素,原子,tail返回去掉第一个元素后的表,相当于括号往里缩一个单位?

是广义表以及递归广义表的原理。 广义表是由n个元素组成的序列,n是广义表的长度。 广义表的深度: 广义表中括号的最大层数叫广义表的深度。 F=(a,F)的长度为2,由于属于递归表,所以深度为无穷,F相当于一个无限的表(a,(a,(a,(...))))。?

F的长度为2,第一个元素是原子,第二个元素是F自身。

F的深度为∞。F=(a,F)=(a,(a,(a,(…))))

对任意一个非空的广义表,其表头可能是单元素,也可能是广义表,而其表尾一定是广义表。注意表尾的深度(即括号的嵌套层数),表尾是由除了表头以外的其余元素组成的广义表,所以,需要在表尾的直接元素外面再加一层括号。
广义表最基本的操作:取表头head(LS)与取表尾tail(LS)

例:LS=(a,(b,c,d))
head(LS)=a
tail(LS)=((b,c,d))
head(tail(LS))=(b,c,d)
tail(tail(LS))=()
head(head(tail(LS)))=b
tail(head(tail(LS)))=(c,d)
head(tail(head(tail(LS))))=c
tail(tail(head(tail(LS))))=(d)
head(tail(tail(head(tail(LS)))))=d
tail(tail(tail(head(tail(LS)))))=()

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