精华内容
下载资源
问答
  • 核心知识点null异常处理dummy node 哑巴节点双指针/快慢指针插入一个节点到排序链表从一个链表中移除一个节点翻转链表合并两个链表找到链表的中间节点例题:83. 删除排序链表中的重复元素给定一个排序链表,删除所有...

    核心知识点

    • null异常处理
    • dummy node 哑巴节点
    • 双指针/快慢指针
    • 插入一个节点到排序链表
    • 从一个链表中移除一个节点
    • 翻转链表
    • 合并两个链表
    • 找到链表的中间节点

    例题:

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

    给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
    示例 1:
    输入: 1->1->2 输出: 1->2 示例 2:
    输入: 1->1->2->3->3 输出: 1->2->3

    直接法:

    链表是有序的,所以直接更改当前结点的 next 指针,跳过下一个结点并直接指向下一个结点之后的结点即可。

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode* deleteDuplicates(ListNode* head) {
             ListNode *current=head;
             //null异常处理
             while(current!=NULL&&current->next!=NULL)
             {
                 //一直删除,直到下一个不重复 
                 // 想想如果把while改成if怎么样
                 //把current->next!=NULL删除会怎么样
                 while(current->next!=NULL&&current->val==current->next->val)
                 {
                     current->next=current->next->next;
                 }
                 //移动到下一个节点
                 current=current->next;
             }
             return head;
     
     
         }
     };
    
    • 时间复杂度:O(n),因为列表中的每个结点都检查一次以确定它是否重复,所以总运行时间为 O(n),其中 n是列表中的结点数。
    • 空间复杂度:O(1),没有使用额外的空间。

    82. 删除排序链表中的重复元素 II

    给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
    示例 1:
    输入: 1->2->3->3->4->4->5 输出: 1->2->5 示例 2:
    输入: 1->1->1->2->3 输出: 2->3

    利用哑结点:

    为了防止删除头结点的极端情况发生,先创建空结点dummy,使dummy指向传入的head结点。

    然后创建一个cur指针指向dummy,比较cur的后两个结点,看他们是否相同。

    如果相同,则说明cur后有重复元素,此时创建一个temp指针指向第一个重复元素,即cur->next;

    通过循环进行去重,循环结束后temp指向的是这群重复元素的最后一个,依照题意此时temp的下一个才是我们想要的。

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode* deleteDuplicates(ListNode* head) {
             //设置哑结点 防止删除头结点的情况发生后的问题
             ListNode *dummy=new ListNode(-1);
             dummy->next=head;
             ListNode *cur=dummy;//cur 指向哑结点
     
             while(cur->next!=NULL&&cur->next->next!=NULL)
             {
                 //比较cur后两个结点
                 if(cur->next->val==cur->next->next->val)
                 {
                     //去重
                     ListNode *temp=cur->next;
                     while(temp->next!=NULL&&temp->val==temp->next->val)
                     {
                         temp=temp->next;
                     }
                     //temp前的重复结点都跳过了,现在我们跳过temp
                     cur->next=temp->next;
                 }
                 else
                 {
                     //如果cur后两个结点不重复,直接前移
                     cur=cur->next;
                 }
             }
             return dummy->next;
         }
     };
    
    • 时间复杂度:O(n)
    • 空间复杂度:O(1)

    206. 反转链表

    反转一个单链表。示例:
    输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

    双指针

    如图,定义两个指针,pre在前 cur在后,temp 保存向前的pre指针的临时指针

    每次进行一次局部翻转,

    当pre到达尾部的时候中止,此时cur指向最后一个节点。

    1b1e55fd02bbac1d2dbece9f321e7166.gif
     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode* reverseList(ListNode* head) {
             /*定义两个指针,pre在前 cur在后
              *当pre到达尾部的时候中止,此时cur指向最后一个节点
              */
             ListNode *pre=head;
             ListNode *cur=NULL;
             ListNode *temp=NULL;
             while(pre!=NULL)
             {
                 temp=pre;//临时存储pre
                 pre=pre->next;//pre指向下一个节点
                 temp->next=cur;//翻转指针
                 cur=temp;//cur指针向前移动一步
             }
             return cur;
     
         }
     };
    

    92. 反转链表 II

    反转从位置 mn 的链表。请使用一趟扫描完成反转。说明: 1 ≤ mn ≤ 链表长度。示例:
    输入: 1->2->3->4->5->NULL, m = 2, n = 4
    输出: 1->4->3->2->5->NULL

    迭代法:

    参考上题,先遍历到 m 处,再翻转

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode* reverseBetween(ListNode* head, int m, int n) {
             if(head==NULL)
                 return NULL;
     
             ListNode *pre,*cur;
             pre=head;
             cur=NULL;
             
             //遍历到m节点,如果只有一个节点,跳过,这里cur会为空但是后面翻转链表的时候就不是了
             while(m>1)
             {
                 cur=pre;
                 pre=pre->next;
                 m--;
                 n--;
                 
             }
     
             //m节点的前一个节点
             ListNode*con=cur;
             ListNode*temp=NULL;
             //用于保存被翻转链表的第一个节点
             ListNode*front=pre;
             
           
             
             //反转m-n的节点
             while(n--)
             {
                 temp=pre;
                 pre=pre->next;
                 temp->next=cur;
                 cur=temp;
             }
             
             //如果不只是一个节点,那么就把指针指向被翻转的链表的最后一个节点
             if(con!=NULL)
             {
                 con->next=cur;
             }
             else
             {
                 //否则直接输出此节点
                 head=cur;
             }
             //被翻转的链表原来的头变尾
             front->next=pre;
             return head;
         }
     };
    

    21. 合并两个有序链表

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    示例:
    输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4

    迭代法:

    直接连接各个节点

     /**
      * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
     
             ListNode *dummy=new ListNode(-1);
             ListNode *cur=dummy;
             //将小的节点接到哑结点为头的链表中
             while(l1!=NULL&&l2!=NULL)
             {
                 if(l1->val>l2->val)
                 {
                    cur->next=l2;
                    cur=cur->next;
                    l2=l2->next;
                 }
                 else
                 {
                     cur->next=l1;
                     cur=cur->next;
                     l1=l1->next;
                 }
     
             }
             
             //处理剩下的节点
             if(l1!=NULL)
             {
                 cur->next=l1;
             }
             if(l2!=NULL)
             {
                 cur->next=l2;
             }
             return dummy->next;
     
         }
     };
    

    86. 分隔链表

    给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
    你应当保留两个分区中每个节点的初始相对位置。
    示例:
    输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5

    当头节点不确定的时候,使用哑巴节点

    将大于 x 的节点,放到另外一个链表,最后连接这两个链表

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode* partition(ListNode* head, int x) {
             if(head==NULL)
                 return head;
             ListNode *headDummy=new ListNode(-1);
             ListNode *tailDummy=new ListNode(-1);
             ListNode *cur=NULL,*tail=tailDummy;
             headDummy->next=head;
             
             head=headDummy;
             
             while(head->next!=NULL)
             {
                 if(head->next->val<x)
                 {
                     head=head->next;
                 }
                 //这里把大于X的节点删除,然后连接到另一个链表
                 else
                 {
                     cur=head->next;
                     //删除大于X的节点
                     head->next=head->next->next;
                     //连接到新链表
                     tail->next=cur;
                     tail=tail->next;
     
     
                 }
             }
             //拼接两个链表
             //tail代表tailDummy最后一个节点,它的后面可能还连着,要断掉
             //如输入[1,4,3,2,5,2]就会有错,没有处理5->2
             tail->next=NULL;
             
             head->next=tailDummy->next;
             return headDummy->next;
     
             
         }
     };
    

    876. 链表的中间结点

    给定一个带有头结点 head 的非空单链表,返回链表的中间结点。
    如果有两个中间结点,则返回第二个中间结点。
     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode* middleNode(ListNode* head) {
             ListNode *slow,*fast;
             slow=head;
             fast=head;
             while(fast!=NULL&&fast->next!=NULL)
            {
                slow=slow->next;
                fast=fast->next->next;
            }
            return slow;
     
         }
     };
    

    总结:如果链表长度是偶数,返回中间偏右的位置

    且fast如果初始化为head->next 返回中间偏左的位置。

    奇数长度则两者相同。

    148. 排序链表

    在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
    示例 1:
    输入: 4->2->1->3 输出: 1->2->3->4 示例 2:
    输入: -1->5->3->4->0 输出: -1->0->3->4->5

    递归

    归并排序链表,找中点和合并操作

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode* sortList(ListNode* head) {
             return mergeSort(head);
     
         }
         //寻找链表中点,快慢指针,快的到达终点,慢的刚好到中点 
         //当链表的长度是奇数时,slow 恰巧停在中点位置;如果长度是偶数,slow 最终的位置是中间偏右:
         //此题我们让head先走,则停在中间偏左的位置
         //148 143 141都有快慢指针
         ListNode *findMiddle(ListNode *head)
         {
             ListNode *slow,*fast;
             slow=head;
             fast=head->next;
             while(fast!=NULL&&fast->next!=NULL)
     
             {
                 slow=slow->next;
                 fast=fast->next->next;
     
             }
             return slow;
         }
         //合并两个链表,参考归并排序
         ListNode * mergeTwoLists(ListNode*left,ListNode*right)
         {
             ListNode *dummy=new ListNode(-1);
             ListNode *head=dummy;
             while(left!=NULL&&right!=NULL)
             {
                 if(left->val>right->val)
                 {
                     head->next=right;
                     right=right->next;
                 }
                 else
                 {
                     head->next=left;
                     left=left->next;
                 }   
                 //下一个
                 head=head->next;
             }
             //处理剩下节点
             while(left!=NULL)
                 {
                     head->next=left;
                     head=head->next;
                     left=left->next;
                 }
                 while(right!=NULL)
                 {
                     head->next=right;
                     head=head->next;
                     right=right->next;
                 }
             return dummy->next;
         }
         
         ListNode *mergeSort(ListNode *head)
         {
             if(head==NULL||head->next==NULL)
             {
                 return head;
             }
     
             ListNode *middle=findMiddle(head);
     
             // 断开中间节点
             ListNode* tail=middle->next;
             middle->next=NULL;
             //左右分别进行归并排序
             ListNode *left=mergeSort(head);
             ListNode *right=mergeSort(tail);
             ListNode *res=mergeTwoLists(left, right);
             return res;
         }
     };
    

    143. 重排链表

    给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
    示例 1:
    给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:
    给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

    此题目为2019年计算机统考408真题

    思路:找到中点断开,翻转后面部分,然后合并前后两个链表

     /**
      * 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:
         
         //快慢指针找中点,同上一题 
         //148 143 141都有快慢指针
         ListNode * findMiddle(ListNode *head)
         {
             ListNode *slow,*fast;
             slow=head;
             fast=head;
             //如果是偶数个节点,返回中间偏右的位置 
             //你改成fast=head->next返回中间偏左也是对的
             //有趣吧,画个图就知道了
             while(fast!=NULL&&fast->next!=NULL)
             {
                 slow=slow->next;
                 fast=fast->next->next;
             }
             return slow;
     
         }
         
         //合并两个链表
         ListNode * mergeTwoLists(ListNode* l1,ListNode*l2)
         {
             ListNode* dummy=new ListNode(-1);
             bool  toggle =true;
             ListNode *head=dummy;
             //间断连接两个链表
             while(l1!=NULL&&l2!=NULL)
             {
                 if(toggle)
                 {
                     head->next=l1;
                     l1=l1->next;
                 }
                 else
                 {
                     head->next=l2;
                     l2=l2->next;
                 }
                 toggle=!toggle;
                 head=head->next;
             }
             //连接剩下的节点
             while(l1!=NULL)
             {
                 head->next=l1;
                 l1=l1->next;
                 head=head->next;
     
             }
             while(l2!=NULL)
             {
                 head->next=l2;
                 l2=l2->next;
                 head=head->next;
     
             }
             return dummy->next;
         }
         
         void reorderList(ListNode* head) {
             if(head==NULL||head->next==NULL)
                 return ;
             
             //找到中点 断开
             ListNode *middle=findMiddle(head);
             ListNode *tail=middle->next;
             middle->next=NULL;
             //翻转链表
             ListNode *cur,*pre;
             pre=tail;
             cur=NULL;
             while(pre!=NULL)
             {
                 ListNode *temp=pre;
                 pre=pre->next;
                 temp->next=cur;
                 cur=temp;
             }
             tail=cur;
             
             //合并链表
             head->next=mergeTwoLists(head,tail)->next;                
         }
         
     };
    

    141. 环形链表

    给定一个链表,判断链表中是否有环。
    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
    示例 1:
    输入:head = [3,2,0,-4], pos = 1
    输出:true
    解释:链表中有一个环,其尾部连接到第二个节点。

    edbfcb09384698f52922348f19e8db21.png


    示例 2:
    输入:head = [1,2], pos = 0
    输出:true
    解释:链表中有一个环,其尾部连接到第一个节点。

    fde0ce43c70d3ebcb17be4d8b23373e8.png


    示例 3:
    输入:head = [1], pos = -1 输出:false 解释:链表中没有环。

    ebbf70d0a96fd51c8d547990eba4d6e0.png

    快慢指针即可,就像你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     //148 143 141 142都有快慢指针
     class Solution {
     public:
         bool hasCycle(ListNode *head) {
             if(head==NULL)
                 return false;
             ListNode *fast,*slow;
             slow=head;
             fast=head;
             while(fast!=NULL&&fast->next!=NULL)
             {
                 slow=slow->next;
                 fast=fast->next->next;
                 // 比较指针是否相等
                 if(slow==fast)
                     return true;
             }
             
             return false;
         }
     };
    

    142. 环形链表 II

    给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
    说明:不允许修改给定的链表。
    示例 :
    输入:head = [3,2,0,-4], pos = 1 输出:tail connects to node index 1 解释:链表中有一个环,其尾部连接到第二个节点。

    edbfcb09384698f52922348f19e8db21.png

    Floyd 算法

    你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她。此题分为两个阶段,第一个阶段先用快慢指针测试是否有环,第二阶段慢指针回到头head,然后各自以相同速度前进,相遇点即为入环处(可以自己画图尝试)。严格的数学证明可参考leetcode官方题解。

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         ListNode *detectCycle(ListNode *head) {
             if(head==NULL)
                 return NULL;
             ListNode *slow,*fast;
             slow=head;
             fast=head;//如果这里是fast=fast->next,那么下面该怎么改?
             while(fast!=NULL&&fast->next!=NULL)
             {
                 slow=slow->next;
                 fast=fast->next->next;
                 if(slow==fast)
                 {
                     //回到起点,各自以相同速度前进
                     slow=head;
                     while(slow!=fast)
                     {
                         slow=slow->next;
                         fast=fast->next;
     
                     }
                     return slow;
                 }                        
             }     
             return NULL;
         }
     };
    

    234. 回文链表

    请判断一个链表是否为回文链表。示例 1:
    输入: 1->2
    输出: false示例 2:
    输入: 1->2->2->1
    输出: true

    先找到链表中点,然后后面的翻转链表,一个个比较。

     /**
      * Definition for singly-linked list.
      * struct ListNode {
      *     int val;
      *     ListNode *next;
      *     ListNode(int x) : val(x), next(NULL) {}
      * };
      */
     class Solution {
     public:
         bool isPalindrome(ListNode* head) {
             if(head==NULL||head->next==NULL)
                 return true;
             ListNode *slow,*fast;
             slow=head;
             fast=head->next;
             while(fast!=NULL&&fast->next!=NULL)
             {
                 slow=slow->next;
                 fast=fast->next->next;
             }
             //偶数长度slow是中间偏左的节点
             //奇数长度slow是中点
     
             ListNode *cur,*pre,*tail,*temp;
             //分离两个链表
             tail=slow->next;
             slow->next=NULL;
             //翻转链表
             pre=tail;
             cur=NULL;
             while(pre!=NULL)
             {
                 temp=pre;
                 pre=pre->next;
                 temp->next=cur;
                 cur=temp;
             }
             //原链表的最后一个节点现在变成头结点
             tail=cur;
     
             while(head!=NULL&&tail!=NULL)
             {
                 if(tail->val!=head->val)
                 {
                     return false;
                 }
                 head=head->next;
                 tail=tail->next;
     
             }
             return true;
     
         }
     };
    

    138. 复制带随机指针的链表

    给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
    要求返回这个链表的 深拷贝。
    我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
    val:一个表示 Node.val 的整数。 random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

    复制节点跟在原节点后面即可

     /*
     // Definition for a Node.
     class Node {
     public:
         int val;
         Node* next;
         Node* random;
         
         Node(int _val) {
             val = _val;
             next = NULL;
             random = NULL;
         }
     };
     */
     
     class Solution {
     public:
         Node* copyRandomList(Node* head) {
             if(head==NULL)
                 return head;
             auto cur=head;
             //复制节点到后面
             while(cur!=NULL)
             {
                 auto clone=new Node(cur->val);
                 clone->next=cur->next;
                 clone->random=cur->random;
                 cur->next=clone;
                 cur=clone->next;
             }
              //处理random指针
             cur=head;
             while(cur!=NULL)
             {
                 if(cur->random!=NULL)
                 {
                     cur->next->random=cur->random->next;
                 }
                 cur=cur->next->next;
             }
             //分离链表
             cur=head;
             auto cloneHead=cur->next;
             while(cur!=NULL&&cur->next!=NULL)
             {
                 auto temp=cur->next;
                 cur->next=cur->next->next;
                 cur=temp;
                 
             }
             return cloneHead;
         }
     };
    
    展开全文
  • 阅读本文约需要10分钟,您可以先关注我们或...01 简介链表就是链式存储的线性表,它最大的优点在于可以有效利用零碎的内存空间,根据链表指针域的不同链表分为单向链表、双向链表等。其实Python语言的列表类型的工作...
    ec71a68f3f30864a438cccb47412be9e.gif

    阅读本文约需要10分钟,您可以先关注我们或收藏本文,避免下次无法找到。

    之前我们通过趣味图解法为大家介绍了二分查找的算法,今天我们一起来学习日常工作中经常能用到的算法链表。

    成哥就是通过这个算法解决了网络ACL策略配置前后插入下发的问题。

    01 简介

    链表就是链式存储的线性表,它最大的优点在于可以有效利用零碎的内存空间,根据链表指针域的不同链表分为单向链表、双向链表等。

    其实Python语言的列表类型的工作原理就是链表。本文章中我们将通过Python来模拟链表结构。但由于Python没有指针概念,我们将通过模拟指针的方法来实现链表。

    02 单向链表

    (1)单向链表简介

    链表的每个元素不仅要存储这个元素值还要存储与这个元素相连的元素的指针值,这样才能实现链表的串联。

    单向链表的每个元素包含一个本身的值和一个指向下一个数的指针。

    这边要注意一下链表最后一个元素是没有指针的所以其指针为空指针。

    f855f064deaaac80c3a45b5d6a561869.png

    如上图,从第一个元素开始,跟着指针箭头走直到没有存储下一个元素指针的最后一个数60为止,就完成了单链表的遍历。

    好了我们现在了解了单链表的大概实现原理,现在我们看看如何用python代码来实现链表,具体代码如下:

    25b1806f05298e24d7831e5e4de43c0c.png

    输出结果如下:

    78fb4dec6786b71f0b9c708e58e2105e.png

    (2)单向链表元素插入

    上面章节我们了解了单向链表的实现原理,本章节我们看看单向链表怎么添加元素。如下图我们该怎么把元素35插入30与40这两个元素之间呢?

    0db4700cb5c7544a41fa7bd9a30a3468.png

    好了不卖关了我们可以先把35元素的指针指向它所要插入的位置后面一个元素40,如下图所示

    9b1fb908c03e67d75ce8d26dc791ec02.png

    接着把需要插入元素前面的元素指针指向该元素,也就是把30的指针指向35,这样就完成了链表的插入如下图所示

    2285838c48e23806034e34c7814ccd61.png

    这时肯定会有读者问为什么要先把新插入元素的指针指向后一个元素,可不可以先把前一个元素30的指针指向35,其实答案是不可以的,当我们先把元素30的指针指向35,这时新元素35还没指向任何元素这将导致链表的断链,具体如下图所示:

    6719457ec10f799ff4873fe09c7a9cc3.png

    下面我们看看如何通过代码实现链表元素的插入吧,代码示例如下:

    115fb83c10c2b0f48e341b39351b5196.png

    输出结果如下:

    d7674f4d57d9d951cf2b1035648a4e8f.png

    (3)单向链表元素删除

    如下图我们可以发现单向链表元素删除非常简单,直接通过当前元素指向下一个元素的指针来找到下一个元素位置,然后把这个位置赋值给当前元素的指针,这样当前元素的指针就会跳过下一个元素直接连接了下下个元素,这就完成了元素的删除具体如下图:

    99eb152757b46bef3f58bc757a13dced.png

    单链表元素的删除具体代码实现如下:

    e4eb23cb3f0d1e97edb96af183c98a17.png

    代码输入如下,可以发现元素50已经被删除,同时链表也可以正常按顺序输出:

    009656345388e1c7bbf593a84e07fec4.png

    03 双向链表

    (1)双向链表简介

    上面我们讲了单链表,现在我们一起来学习一下链表的另一种类型双链表,双链表的每个元素是由它的值和两个指针组成,一个指针指向上一个元素,一个指针指向下一个元素。双链表比起单链表的优势是可以进行双向遍历,如下图所示:

    a2f1c353819b04086ff1c52091b7ee93.png

    下面我们就通过Python代码来模拟一下双向链表的双向的链表输出

    9d03bb4e4774182955d7d0ee8671f54c.png

    代码运行结果输出如下:

    0fbe75d957627b4e15d8caf5cfa1d77a.png

    (2)双向链表元素插入

    通过上面章节我们了解了双向链表的实现原理,现在我们再来看看对双向链表进行元素插入吧。

    05614687d4ef03273f6fe1bc9dd98901.png

    如上图第一步我们先对新插入的元素的两个指针赋值,分别将它们指向插入位置的后一个元素与前一个元素,接着第二步将后一个元素前指向指针与前一个元素后指向指针赋值指向新插入的元素,这样我们就完成了双向链表的元素插入。双链表比起单链表好处就是可以通过知道上一个元素的位置来插入新元素,也可以通过知道下一个元素的位置来插入新元素。在日常工作中双向链表适用范围比单向链表广,之前我们项目中就是用的双向链表来对ACL策略进行配置顺序调整的。

    下面我们通过Python代码来实现双向链表的元素插入吧

    65c3fce853ecdd068722279220a5d9aa.png

    代码执行结果如下,发现链表插入元素35后正反向都能正确进行遍历

    aace6a8cd6a56abec1cd93005e60adde.png

    (3)双向链表元素删除

    双链表的删除其实和单向链表类似,我们要知道删除元素的前一个数的位置,然后通过要删除的元素来确定下下一个元素的位置,最后直接连接要删除的元素的前后两个数就完成了删除,如下图所示:

    2688b718a8b809cf10abf25e9e1f44e9.png

    现在我们看看如何通过代码实现双向链表的元素删除吧

    4c431c2e7dbe74c376c3f272555fc605.png

    代码输入结果如下,发现元素35已经正确的删除了

    4ee8e9a71ec6ef99273a1fd537b47c53.png

    至此我们的链表算法就讲完了,如果大家喜欢不要忘了点击@IT管理局关注、点赞与收藏哦!

    本局精彩文章:

    • 趣味图解算法之二分查找
    • Wireshark数据包分析三板斧
    • IT工程师都需要掌握的容器技术之扫盲篇
    展开全文
  • 一、题目:入一个链表输出链表中倒数第k个结点。刚开始看到这道题的时候完全没有一点思路因为我的 算法基础还是比较薄弱的, 但对于一些算法大佬这种题目那是看一下就知道怎么去写了,对于我来说还是有些难度的...

    57a9cea66cb85374a5a16c59a2042052.png

    个人观点:工作这么这么久虽然工作上用的算法不多,但却让我感到学好数据结构和算法对于一个程序员事多么的重要,至少你是个有思想的程序员而不是只是复制粘贴的码农,那话不多说看看这道题的解法吧!

    一、题目:入一个链表,输出该链表中倒数第k个结点。

    刚开始看到这道题的时候完全没有一点思路因为我的 算法基础还是比较薄弱的, 但对于一些算法大佬这种题目那是看一下就知道怎么去写了,对于我来说还是有些难度的。

    参考剑指off上一些大佬的写法从中能到一些思路,画了一个简单的草图比较丑 。

    aacf18164b54ea561c99f59f8339f6bc.png

    这是个人觉得比较好理解的思路拿过来分享一下。

    二、解题思路

    • 1.传统的我们可以这么理解,比如在二个一样长的木桥上有两个人站在桥头要求出桥倒数第k步的位置在那? 解:我们可以先让第一个人先走k步,那么剩余的步数就是n-k步,当第一个人走到k步的位置时,第二个人和第一人同时走,当第一个人走完的时候,第二个人停住,停住的地方即为倒数第k步的位置。
    • 此题感觉可以拿来作为一个测试题来发挥自己的想象。
    • 2.正常的思路理解,设链表的长度为N。设置两个指针p1和p2,先让p1移动k个节点,则还有n-k个节点可以移动,此时让p1和p2同时移动,可以知道当p1移动到链表的结尾时,p2移动到n-k个节点处,该位置就是倒数第k个节点。

    三、代码实现

    public class Solution {
        public ListNode FindKthToTail(ListNode head,int k) {
            //判断头指针是否为空
            if(head == null)
                return null;
            //设置p1指针为头指针
            ListNode p1 = head;
            while(p1 != null && k-- >0)
                //p1移动k个节点
                p1 = p1.next;
             //如果没有移动完k个节点则返回空
            if(k > 0)
                return null;
             //设置p2指针为头指针
            ListNode p2 = head;
            //当p1等于空的时候结束移动
            while(p1 != null){
                p1 = p1.next;
                p2 = p2.next;
            }
            //则p2就是倒数第k个节点
            return p2;
        }
    }

    四、总结

    这道题还是相对比较简单的从这道题的解题思路类似于数学上的对称,那个利用两个指针对开始的地方走k步即是到过来的k步,但是我们怎么得到呢?

    利用两个指针思想还是非常的巧妙的。用第二个指针记录第一个指针从第k个位置走完的位置即第二个指针走完n-k个位置那第二个指针的位置就是倒数第k个位置。从这个思想上我们扩散出许多的题目类型,也可以让自己的思维跳出局限。

    展开全文
  • 与去年相比,21江苏省考招录人数和岗位都增加了1000+人,但是报名人数增加了10万多人。...最后一个月准备怎么冲刺呢?刷题最后能提高几分?在最后一个月的备考中,有些同学会大量刷题,秉承着“量的飞跃终究成...

    与去年相比,21江苏省考招录人数和岗位都增加了1000+人,但是报名人数增加了10万多人其中,南京的竞争压力最大,不仅是报名人数最多,平均岗位竞争比也达到了115:1;其次就是省直机关,报名总人数为13622人,比去年多了6000+人。小编只能说今年的竞争还是很大的,小伙伴们准备好了吗?最后一个月准备怎么冲刺呢?

    97a8f2556b1e3ca62d539c47b753f61e.png

    刷题最后能提高几分?

    在最后一个月的备考中,有些同学会大量刷题,秉承着“量的飞跃终究成就质的飞跃”,似乎题目做多了,水平也就自然而然的提升,其实不然,光做题,不梳理,知识点在脑海中还是一团乱麻;做题到最后却没有找到自己的“薄弱环节”,这样一来,岂不是浪费时间和题目。比如,申论的分数不高,就要分析哪一部分得分低,寻找题目的突破点,否则盲目刷题而不知道总结,最终也没有找到提高分数的突破点。

    db145ba79c3d1599afb92ce6a8093d8c.png

    考试如何省时间?

    解题技巧就是一把锋利的“破冰刀”,比如:如何快找言语理解中关键词,判断推理中如何快速确定基本点……这些都有技巧。

    考试中的时间是有限的,如果充分运用娴熟的解题技巧,不仅可以节省更多的时间,还能保证高正确率。

    百人竞争一个岗位,压力大吗?那是肯定的。距离江苏省考还有一个月的时间,要怎么备考呢?疯狂刷题?总结?其实在备考的最后阶段,更重要的是“保持一个良好的心态”。

    私信小编,回复:公考,获取公考公文备考金句。

    c6c058b5d090e4954bc2535079e0a0b6.png
    展开全文
  • 那么2020年初级会计考试最后一个星期怎么复习?答题技巧有哪些?会计网整理了相关内容,来了解下吧! 初级会计师考试考前一周复习方法 1、梳理知识框架,串联各章节知识点 初级会计复习技巧有哪些?到了初级会计考试...
  • 那么,孩子怎么摆脱吃喝玩睡的恶性循环?别担心,现在要为孩子制定一个“靠谱”的暑期规划,前一个月的‘散养’生活已经告一段落接下来就要为开学做准备了!第一阶段:“圈养”阶段,查缺补漏好时机时间段:暑假中期...
  • 美剧《最后一个男人》,完全没有末日的氛围,反而是一部轻喜剧。如果全世界只剩下你这个人了,你会做什么?挑选一个大的别墅居住,闯进一家超市随意采购,把一个泳池当便池等等,很多疯狂的事情,都是男主刚开始做的...
  • 之前怎么做的,现在继续怎么做,保持一颗平常心就行。 有些人或事就是这样,你越放在心上,你越放不下心。 就像我之前失眠一样,经常大半夜睡不着,第二天一大早起来就想今晚该怎样才能让自己快速入眠......天天想...
  • 利用Java怎么链表输出到倒数第k个节点发布时间:2020-12-08 16:49:33来源:亿速云阅读:53作者:Leah利用Java怎么链表输出到倒数第k个节点?很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为...
  • (2)能够访问到链表中的每一个节点,即输出每个节点的数据,这种操作称为遍历,。(3)能够通过数据,查找到节点所在位置。(4)能够在链表任意位置插入一个节点。(5)能够在链表任意位置删除一个节点。(6)能够在程序结束...
  • 从尾到头输出链表

    2015-01-07 19:02:00
    从头到尾的输出链表对于大家来说都是比较简单的,但是从尾到头应该怎么做好呢? 其实可以这样想,从头到尾输出链表,并把链表的数据存放到栈中,当遍历到链表尾部的时候,再从栈中输出数据,此时得到的值就是从尾...
  • 链表输出怎么

    2014-08-14 18:23:32
    #include #include #define NULL 0 struct st { int num; struct st *next; }; int n=0; void creat() ... /就是这一段,我明明把头结点给了p1,为什么还是输出不了/ } void main() { creat(); }
  • 5输出:5->4->3->2->1难点如果换成数据反转,你会吗(傻子才不会)。按照常规思维,链表反转需要知道最后一个元素,然后从最后一个元素依次往前找,直到遍历到第一个元素即完成反转。但是这里并不是双向...
  • void printf_node_fun(ListLink head) 30 { 31 ListLink p = head; 32 while(1) 33 { 34 if(p == NULL) 35 { 36 printf("p is NULL");...每次输出都只输出最后输入的那个而已,是怎么回事??
  • 链表输出怎么改?

    2014-07-13 10:31:49
    #include #include #define NULL 0 struct st { int num; struct st *next; }; int n=0; void creat() ... /就是这一段,我明明把头结点给了p1,为什么还是输出不了/ } void main() { creat(); }
  • 题目描述定义一个函数,输入一个链表的头节点,反转该链表输出反转后链表的头节点。示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL解题思路方法1:暴力法方法2:双指...
  • else//如果链表2的当前节点指数小,那么要把链表2的当前节点加入到结果链表中(即是链表1) { u=q->link; q->link=p; pre->link=q; pre=q; q=u; } if(q)//如果链表2比...
  • 怎么在类中建立动态链表,再把链表输出.
  • 题目:输入一个单向链表输出链表中倒数第 k 个结点。 方案一:先遍历一遍,获取到链表的长度n,然后从头再走n-k步。分析:相当于遍历两遍,第一遍是为了获得链表的长度,而第二遍是找到倒数第k个节点。 方案二...
  • #include<stdio.h> #include<cstdlib> #include<conio.h> #include<malloc.h> typedef int ElemType; typedef int Status; typedef struct LNode{ ElemType data;...
  • 【问题描述】学习链表,销毁链表总感觉没有成功,请问怎么确定链表确实被销毁了?为什么其余节点的内容没有变化? 【代码】 ``` #include #include #include struct link_list { int num; char name[20...
  • 今天在牛客网上做了一个算法题,不知道是不是一孕傻三年的原因,竟然被一道难度为简单的算法题难住了。...于是我觉得我想多了,这是个算法题怎么可能考察lamda表达式,傻帽儿。 我看了一下左边,原来有个说
  • 两个非降序链表的并集,例如将链表1->2->3 和 2->3->5 并为 1->2->3->5,只能输出结果,不能修改两个链表的数据。 #include #include typedef int DataType; typedef struct node { DataType data; ...
  • 这个怎么改,并且说一下为什么要这样改,谢谢 #include <stdio.h> #include <string.h> #include <stdlib.h> void input(); void output(); void save(); void load(); typedef ...
  • 一、题目:入一个链表输出链表中倒数第k个结点。刚开始看到这道题的时候完全没有一点思路因为我的 算法基础还是比较薄弱的, 但对于一些算法大佬这种题目那是看一下就知道怎么去写了,对于我来说还是有些难度的...
  • 我觉得链表没问题,是不是指针有什么问题…… ``` #include #include using namespace std; class song{ int id; char* name; public: char* get(){return name;} song(){}; song(int a,char* b){ id=a; ...
  • 我是根据这个题目的要求来写了一个双链表,然后利用gb表示光标实现各个符号的插入,可是有的时候能输出正确的结果,有的时候会输出乱码,有的时候不输出,这是怎么回事啊,不知道哪个代码块出现了问题,求大神解答!...
  • 利用Java怎么实现一个反转链表发布时间:2020-12-08 16:46:18来源:亿速云阅读:99作者:Leah今天就跟大家聊聊有关利用Java怎么实现一个反转链表,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下...
  • 例42:C语言实现一个简单链表,它由3个学生数据的结点组成,要求输出各结点中的数据。解题思路:读者在学习这道例题的时候,应该首先分析三个问题。各个结点是怎么样构成链表的?没有头指针head行不行?p起什么作用...
  • 4输出:1->1->2->3->4->4这个是一个典型的链表问题,链表的问题相对来说还是比较简单的,但是确实很让人头疼,尤其是像C++这类语言,经常需要自己手动释放内存。而且经常就会出现野指针问题。...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 361
精华内容 144
关键字:

怎么输出链表