数据结构-链表篇_第2梦的博客-程序员秘密

技术标签: 链表算法题总结  翻转链表  数据结构与算法  数据结构  

一、链表基础

创建、销毁、插入、删除,对于链表这些最基础的操作,我们还是必须掌握的

1、定义链表数据结构

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

2、创建链表

创建一个链表,并用一个数组初始化链表。

ListNode* CreateList(int* arr,int size)
{
    ListNode *rootnode = NULL, *tmproot =NULL;
    for (int i = 0; i <size; i++)
    {
        if (i == 0)
        {
            rootnode = new ListNode(arr[i]);
            tmproot = rootnode;
        }
        else
        {
            ListNode *node = new ListNode(arr[i]);
            rootnode->next = node;
            rootnode = rootnode->next;
        }
    }
    rootnode->next = NULL;
    return tmproot;
}

3、删除节点

常规方法是从头头遍历,找到需要删除的解决点的前面一个节点,进行删除:

pre->next=pre->next->next
delete cur;

注意:
1)传入链表参数时,如果传指针,一定要是双指针,不然是没用的,原因应该不用我说吧;当然也可以传单指针时,返回。反正就是要让读链表的操作生效;
2)检查是否为空时,不仅要检出head,也要检查其解引用*head,是否为空;
3)注意头结点的处理,当然你可以增加一个辅助头结点,然后让辅助头结点指向头结点,那么所有节点操作都一样了,不然就要特殊处理下;
4)一定要记得delete掉欲删除的节点,不然一直在内存中。
上述四点特别容易忽视,一定一定要注意。

完整代码:

void DeleteNode(ListNode **head,int target)
{
    if(head==NULL||*head==NULL) return; 
    ListNode *delnode;

    if((*head)->val==target)
    {
        delnode=*head;
        *head=(*head)->next;    
    }
    else
    {
        ListNode *phead=*head;
        while (phead->next!=NULL&&phead->next->val!= target)
        {
            tmphead = tmphead->next;
        } 
        if (phead->next!=NULL&&phead->next->val == target)
        {
            phead->next = phead->next->next;    
            delnode=phead->next;        
        }
    }
    if(phead!=NULL)
    {
        delete delnode;
        delnode=NULL;
    }
}

上面的删除时间复杂度是O(n),其实还有O(1)的解法,不过这个解法是假设链表中一定有这个节点,并且是知道这个节点而不只是这个节点的值。这个删除方法很巧妙,它是让待删除的节点的值等于它的下一个节点值,也就是让下一个节点覆盖这个节点,意义上相当于删除了这个节点。对于要删除的节点是头结点,中间的节点,以及尾节点,要分别讨论

void deleteNode(ListNode **head,ListNode *toDelNode)
{
    if(!head||!*head||!toDelNode) return;
    //要删除的节点不是尾节点
    if(toDelNode->next!=NULL)
    {
        ListNode *pnode=toDelNode->next;
        toDelNode->val=pnode->val;
        toDelNode->next=pnode->next;

        delete pnode;
        pnode=NULL;
    }
    else if(*head==toDelNode)
    {
        *head=(*head)->next;
        delete toDelNode;
        toDelNode=NULL;
    }
    else
    {
        ListNode *ptemp=*head;
        while(ptemp->next!=toDelNode)
        {
            ptemp=ptemp->next;
        }
        ptemp->next=NULL;
        delete  toDelNode;
        toDelNode=NULL;
    }
}

4、插入节点

比如在节点cur后插入一个值为val的节点,伪代码如下:

ListNode *nextnode=cur->next; //先将原来的next保存下来
ListNode *node=new ListNode(val); 
cur->next=node;
node->next=nextnode;

二、链表算法题小技巧

花了几天时间,把链表的题做了下。做多了后,发现,也就那几个点,用来用去,所以有必要总结下。

1、快慢指针

让一个指针走的块,一个走的快,发现这个真是好用,可以干很多事,比如寻找中间节点,比如判断链表是否有环,还比如寻找倒数第k个节点等。

ListNode* fast = head;
ListNode* slow = head;

2、增加辅助头结点

增加一个辅助头节点newhead,在这个头结点基础上操作,得到最终链表,最后返回newhead->next。当原链表要涉及到头结点的操作时,可以使用这个技巧,可以省去很多麻烦。

ListNode* newhead=new ListNode(-1);
newhead->next=head;

三、 常见链表操作

1、寻找中间节点

在数组中寻找中间节点是一件很简单的事情,但是在链表中寻找中间节点却不是那么一蹴而就,怎么快速找到中间节点了,使用技巧——快慢指针,代码如下,能找到中间节点是很多问题的前提,比如链表归并排序等等。

ListNode* findMid(ListNode* head)
{
    if(head==NULL) return;
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast!=NULL&&fast->next!=NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow ;
}

2、翻转链表

这里我们所说的链表都是单向链表,单向链表是“一路向西”的,不可回头,那么翻转链表就成了一个问题,并且会衍生出来好些关于翻转链表的问题,比如翻转链表中从第m个到第n个的节点,再比如每k个为一组进行翻转等等,下面具体来看看各个题目:

2.1、Reverse Linked List

1)问题描述:就是将一个链表翻转。

2)代码:

ListNode* reverseList(ListNode* head)
{
   ListNode* pre=NULL,*cur=head;
   while(cur)
   {
      ListNode* next=cur->next; //先把洗衣歌节点保存下来
      cur->next=pre; //翻转
      //往下走
      pre=cur;
      cur=next;
   }
   return pre; //pre是翻转后的链表的头
}

2.2、Reverse Linked List II

1)问题描述:对m到n这段链表进行翻转。
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.

2)代码:

ListNode *reverseBetween(ListNode *head, int m, int n) 
{
     if(m==n) return head;
     n-=m; //范围
     ListNode prehead(0);
     prehead->next=head;
     ListNode* pre=&prehead;
     while(--m)pre=pre->next;        
     ListNode* pstart=pre->next;
     while(n--)
     {
         ListNode *p=pstart->next;
         pstart->next=p->next;
         p->next=pre->next;
         pre->next=p;
     }
     return prehead.next;
}

2.3、Reverse Nodes in k-Group

1)问题描述:

For example,
Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

2)解决思想:
找到每一个组,然后分别进行翻转。

3)代码:

ListNode* reverseKGroup(ListNode* head, int k) 
{
    ListNode* thead = head;
    int count = 0;
    while (thead)
    {
        count++;
        thead = thead->next;
    }
    for (int i = 1; i <= count; i++)
    {
        if (i%k == 0)
        {
            head = reverseBetween(head, i - k+1, i);
        }
    }
    return head;
  }

四、链表与其他算法综合运用

1、链表插入排序

1)问题描述:
数组插入排序作为最简单的排序算法,大家都比较熟悉了,如果对于排序还不熟悉,可以看看我的另一篇博客:七大排序算法,那么在链表上怎么实现插入排序了。

2)代码:

ListNode* insertionSortList(ListNode* head) 
{
     if (!head) return NULL;

        ListNode *newhead = new ListNode(-1); //增加辅助头节点
        newhead->next = NULL;
        ListNode *tmpnewhead = newhead; //备份一份

        ListNode *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            newhead = tmpnewhead;
            //找插入点
            while (newhead->next&&newhead->next->val <cur->val)
            {
                newhead = newhead->next;
            }
            //将当前节点插入
            cur->next = newhead->next;
            newhead->next = cur;
            //往下走 
            cur = next;
        }
        return tmpnewhead->next;   
 }

2、判断是否是回文链表

1)问题描述:
回文大家知道是啥意思吧,就是从左到右和从右到左看是一样的,也可以说是对称的。

2)解决思想:
链表判断是否是回文链表的思想是将链表后半部分翻转与前半部分比较,如果相同就是回文链表。这里要用到寻找中间节点,和翻转链表。

3)代码:

bool isPalindrome(ListNode* head) 
{
     if(!head||!head->next) return true;
     //寻找中间节点
     ListNode *tmpnode=head;
     ListNode *mid=findMid(tmpnode);     
     //翻转链表后半部分
     ListNode* newhead=reverseList(mid);     
     //比较前半部分和后半部分,看是否相等
     while(head&&newhead) //有这个条件就不同担心链表奇数、偶数个节点了
     {
         if(head->val!=newhead->val)
         {
             return false;
         }
         head=head->next;
         newhead=newhead->next;
     }
     return true;
 }

3、Reorder List

1)问题描述:
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
For example:Given {1,2,3,4}, reorder it to {1,4,2,3}.

2)解决思想:
跟判断是否是回文链表,基本一样,先找到中间节点,然后翻转后半部分链表,再将后一个链表的值逐个插入到前一个链表中。

3)代码:

  void reorderList(ListNode* head) 
    {
        if(!head||!head->next) return;

        ListNode *tmpnode=head;  
        ListNode* mid=findMid(tmpnode);      
        mid=reverseList(mid);

        //插入
        ListNode* fhead=head; //前半部分
        while(fhead&&mid)
        {
            ListNode* fnext=fhead->next;
            ListNode* mnext=mid->next;
            fhead->next=mid;
            mid->next=fnext;

            fhead=fnext;
            mid=mnext;
        }
    }

4、Linked List Cycle

1)问题描述:判断链表中是否有环。

2)解决思想:快慢指针,如果有环,一定会相遇。

3)代码:

bool hasCycle(ListNode *head) 
{
      ListNode *slow=head,*fast=head;
      while(fast&&fast->next)
      {
          slow=slow->next;
          fast=fast->next->next;
          if(slow==fast) 
             return true;
      }
      return false;
  }

5、Rotate List

1)问题描述:
Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

2)解决思想:
先找到倒数第k个节点,然后前后前后半部分换一下。

3)代码:

ListNode* rotateRight(ListNode* head, int k) 
 {
      if(!head||!head->next) return head;

      ListNode* chead=head; //为了计算链表长度用的
      int count=0;
      while(chead)
      {
          count++;
          chead=chead->next;
      }
      //快的先走K步
      ListNode* slow=head,*fast=head;      
      for(int i=0;i<k%count;i++) fast=fast->next;    
      if(fast==head||!fast) return head;  
      //再一起走,那么slow最后就是倒数第K个节点
      while(fast->next)
      {
          slow=slow->next;
          fast=fast->next;
      }

      ListNode* newhead=slow->next; //这就是新的头了
      ListNode* tmpnewhead=newhead; //对newhead备份下
      slow->next=NULL;

      //将原链表倒数k节点前面的链表部分加到新链表后面
      while(newhead->next) newhead=newhead->next;
      newhead->next=head;

      return tmpnewhead;
  }

6、Swap Nodes in Pairs

1)问题描述:
链表中每一对每一对交换位置。

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

2)解决思想:
每两个两个交换,其实还是翻转链表思想。

3)代码:

ListNode* swapPairs(ListNode* head) 
{
     ListNode* newhead=new ListNode(0); //定义一个新的辅助节点在头前面
     newhead->next=head;
     ListNode* renode=newhead; //副本用于返回

     while(newhead->next&&newhead->next->next)
     {
         ListNode* pre=newhead; //pair前面的那个节点
         ListNode* node1=pre->next;
         ListNode* node2=pre->next->next;
         ListNode* behind=node2->next; //pair后面的节点
         node2->next=NULL;

         node1->next=behind;
         pre->next=node2;
         node2->next=node1;

         newhead=newhead->next->next;
     }
     return renode->next;
 }

7、Sort List -链表归并排序

ListNode* mergeList(ListNode* list1, ListNode* list2)
{
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;

    ListNode* head=new ListNode(-1);
    ListNode* tmp=head;

    while (list1&&list2)
    {
        if (list1->val<list2->val)
        {
            tmp->next = list1;
            list1 = list1->next;
        }
        else
        {
            tmp->next = list2;
            list2 = list2->next;
        }
        tmp = tmp->next;
    }
    if (list1) tmp->next = list1;
    if (list2) tmp->next = list2;

    return head->next;
}

ListNode* sortList(ListNode* head)
{
    if (head == NULL || head->next == NULL) return head;

    ListNode* fast = head;
    ListNode* slow = head;
    //如果加上 fast->next->next!= NULL作为条件,比如{
   21}的mid就是NULLwhile (fast->next!= NULL && fast->next->next!= NULL){
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* mid = slow->next;
    slow->next = NULL;

    ListNode* list1 = sortList(head);
    ListNode* list2 = sortList(mid);

    ListNode* sortedlist = mergeList(list1, list2);
    return sortedlist;

}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/yixianfeng41/article/details/52955264

智能推荐

JAVA-25.2-js提高篇、BOM编程、事件编程、DOM编程、js正则表达式、表单验证案例_元_帅的博客-程序员秘密

一、BOM编程  什么是BOM编程?BOM是(Broswer Object Model) 浏览器对象模型编程 1.window对象   open(): 在一个窗口中打开页面     参数一: 打开的页面     参数二:打开的方式。 _self: 本窗口 _blank: 新窗口(默认)     参数三: 设置窗口参数。比如窗口大小   setInterval(): 设置定时器(执行n次

JS DOM编程_Y__J___的博客-程序员秘密

获取文本框&lt;!DOCTYPE html&gt;&lt;html&gt; &lt;head&gt; &lt;meta charset="utf-8"&gt; &lt;title&gt;DOM编程-获取文本框的value&lt;/title&gt; &lt;/head&gt; &lt;body&gt; &lt;script type="text/javascript"&gt...

Web APls_让我再睡会儿呗的博客-程序员秘密

2022.3.26 学习笔记目录四、正则表达式4.1 概述4.2 创建正则表达式的对象4.3 检验是否符合正则表达式4.4 使用字面量创建正则表达式4.4.1 语法: var 变量 = /正则表达式/匹配模式4.4.2 创建一个正则表达式,检查一个字符串中是否含有‘a’或‘b’4.5 字符串和正则表达式相关的方法4.5.1 split( ) 可以将一个字符串拆分成一个数组4.5.2 search( ) 可以搜索字符串中是否含有指定内容4.5.3 match(

JavaScript(二)--BOM编程/事件编程/DOM编程/正则表达式_yangruxi的博客-程序员秘密

BOM编程1.BOM编程图解: 2.window对象: open():在一个窗口中打开页面 参数一: 打开的页面 参数二:打开的方式。 _self: 本窗口 _blank: 新窗口(默认) 参数三: 设置窗口参数。比如窗口大小setInterval():设置定时器(执行n次) setTimeout():设置定时器(只执行1次) 定时器: 每隔n毫秒调用指定的任务(函数) 参数一:指

防火墙的web配置_Sun.1998的博客-程序员秘密_web应用防火墙配置

防火墙:它是一种位于内部网络与外部网络之间的网络安全系统。一项信息安全的防护系统,依照特定的规则,允许或是限制传输的数据通过。防火墙主要由服务访问规则、验证工具、包过滤和应用网关4个部分组成,防火墙就是一个位于计算机和它所连接的网络之间的软件或硬件。该计算机流入流出的所有网络通信和数据包均要经过此防火墙。在网络中,所谓“防火墙”,是指一种将内部网和公众访问网(如Internet)分开的方法,它实际上是一种隔离技术。防火墙是在两个网络通讯时执行的一种访问控制尺度,它能允许你“同意”的人和数据进入你的网络,

随便推点

Postman接口测试工具实战演练集_萌笑天的博客-程序员秘密_postman练习

主要进行工具下载安装以及工具日常测试使用的内容进行讲解,并收录整合成一个合集

如何使用PostMan进行接口测试_qianshanding0708的博客-程序员秘密

更多内容关注微信公众号:fullstack888今天给大家分享的内容是接口测试必备的postman测试工具的使用:postman发送get与post请求,变量的设置与引用,文件的导入与导出...

【JavaScript】页面捕捉和正则表示_执久呀的博客-程序员秘密_js正则捕捉

捕捉键盘回车事件对于keydown事件来说,都有keyCode属性来获取键值(即键盘上的每个键都有对应的一个值)回车键为13,Esc键为27&lt;script type="text/javascript"&gt;//①当页面加载完成,调用这个函数 window.onload=function(){ //②界面捕捉id为username的元素中发生键盘敲下事件是调用这个函数 document.getElementById("username").onkeydown=fu

JavaScript&正则表达式_胖ۣۖ虎ۣۖ的博客-程序员秘密_js文件路径正则表达式

文章目录JavaScript&amp;正则表达式第一章 JavaScript1. 学习目标2. 内容讲解2.1 JavaScript的起源2.2 JavaScript的特性2.2.1 脚本语言2.2.2 基于对象2.2.3 弱类型2.2.4 事件驱动2.2.5 跨平台性2.3 入门程序2.4 JavaScript的基本语法2.4.1 JavaScript的引入方式2.4.1.1 内部脚本方式2.4.1.2 外部脚本方式2.4.2 声明和使用变量2.4.2.1 JavaScript数据类型2.4.2.2 变量

防火墙概述_时不待我。的博客-程序员秘密

防火墙概述目录下一代防火墙的概述1.防火墙的定义1.1什么是防火墙?1.2防火墙的分类1.3防火墙的功能1.4防火墙的安全策略1.4.1防火墙安全策略原理1.4.2防火墙安全策略作用1.4.3防火墙安全策略分类2.防火墙的相关技术2.1包过滤技术2.1.1包过滤的基础2.1.2包过滤防火墙的工作过程2.2会话机制2.2.1状态防火墙原理2.2.2会话表项2.2.3状态检测防火墙的转发机制2.3应用...

推荐文章

热门文章

相关标签