• 力扣-----链表

    目录

    一：创建和打印链表

    二：反转链表 

    三：删除重复的链表 

    四：删除链表的元素 

    法二：设立虚拟头结点

    可以把这个递归思路沿用到--删除重复元素

    五： 两两交换链表节点 

     六：删除结点

    七：删除链表倒数的n个结点

    一：创建和打印链表

     力扣给出的结构体

    1. struct ListNode {
    2.       int val;
    3.       ListNode *next;
    4.       ListNode() : val(0), next(nullptr) {}
    5.       ListNode(int x) : val(x), next(nullptr) {}
    6.       ListNode(int x, ListNode *next) : val(x), next(next) {}
    7. };

    传入一个数组，构建一个链表

    • 值得注意的是链表的第一个元素很重要，必须记录
    • 传入一个链表头结点，就可以遍历出整个链表
    1. /*创建一个链表*/
    2. ListNode* createList(int a[],int n){
    3.     //返回指向链表第一个元素的指针,传入一个数组：数组头指针和数组大小
    4.     if(n==0) return 0;//数组无元素
    5.     /*创建头指针head，这里是指向第一个元素的*/
    6.     ListNode* head=new ListNode(a[0]);
    7.     /*利用该指针，创建好余下数据*/
    8.     ListNode* cur=head;
    9.     for(int i=1;i
    10.         cur->next=new ListNode(a[i]);
    11.         cur=cur->next;
    12.     }
    13.     return head;
    14. }

    由于没有辅助的头结点，类似尾插法，头指针不断在变化，需要格外的引用记录头指针

    • cur->next=new ListNode(a[i]);----------将新结点链入
    • cur=cur->next;---------头结点在变化

    打印一个链表

    1. void printLink(ListNode* head) {
    2.     ListNode* cur=head;
    3.     while(cur){
    4.         cout<val<<"->";
    5.         cur=cur->next;
    6.     }
    7.     cout<<"null"<
    8. }

    二：反转链表 

    链表问题中：一般要求对指针进行操作，而不是链表的值

     分析：

               因为要实现把该结点指针指向其前驱，所以一个指针记录当前结点cur，一个记录cur前一个结点pre.但是这个时候cur没法沿着链条向前移动了，断链了。所以cur的后继suc也需要记录，保证了cur和pre的正常前移。

    模拟

    • 把cur的next指针指向pre，完成单个反转
    • 然后pre指向cur，cur指向suc，suc前移
    1. ListNode* reverseList(ListNode* head) {
    2.          ListNode* pre=NULL;
    3.          ListNode* cur=head;//从第一个结点开始
    4.          while(cur){//不定义suc=head->next,防止不存在造成泄漏
    5.              ListNode* suc=cur->next;//保证了链不断
    6.              /*反转*/
    7.              cur->next=pre;
    8.              /*更新*/
    9.              pre=cur;
    10.              cur=suc;
    11.              //suc=suc->next;没有这句话
    12.          }
    13.          return pre;//pre在结束时，指向了链表的第一个元素
    14.     }

    法二：不把suc视为cur的存在而存在

    1. ListNode* reverseList(ListNode* head) {
    2.          ListNode* pre=NULL;
    3.          ListNode* cur=head;//从第一个结点开始
    4.          if(cur==NULL||cur->next==NULL) return cur;
    5.          ListNode* suc=head->next;
    6.          while(cur){
    7.              /*反转*/
    8.              cur->next=pre;
    9.              /*更新*/
    10.              pre=cur;
    11.              cur=suc;
    12.              if(suc) suc=suc->next;
    13.          }
    14.          return pre;//pre在结束时，指向了链表的第一个元素
    15.     }

    这时候比较需要注意就是：没有NULL->next

    所以每次更新suc需要判断一下自己是否为空，把suc不存在的情况:cur->next或cur为空的情况提前return

     自己的测试台程序测试：

    1. #include
    2. using namespace std;
    3. struct ListNode {
    4.       int val;
    5.       ListNode *next;
    6.       ListNode() : val(0), next(nullptr) {}
    7.       ListNode(int x) : val(x), next(nullptr) {}
    8.       ListNode(int x, ListNode *next) : val(x), next(next) {}
    9. };
    10. /*创建一个链表*/
    11. ListNode* createList(int a[],int n){
    12.     //返回指向链表第一个元素的指针,传入一个数组：数组头指针和数组大小
    13.     if(n==0) return 0;//数组无元素
    14.     /*创建头指针head，这里是指向第一个元素的*/
    15.     ListNode* head=new ListNode(a[0]);
    16.     /*利用该指针，创建好余下数据*/
    17.     ListNode* cur=head;
    18.     for(int i=1;i
    19.         cur->next=new ListNode(a[i]);
    20.         cur=cur->next;
    21.     }
    22.     return head;
    23. }
    24. /*打印一个链表*/
    25. void printLink(ListNode* head) {
    26.     ListNode* cur=head;
    27.     while(cur){
    28.         cout<val<<"->";
    29.         cur=cur->next;
    30.     }
    31.     cout<<"null"<
    32. }
    33. /*为防止内存泄漏，释放节点*/
    34. void deleteNode(ListNode* head){
    35.     ListNode* cur=head;
    36.     while(cur){//当前指向结点不为空
    37.         ListNode* delNode=cur;
    38.         cur=cur->next;//沿着链表移动
    39.         delete delNode;
    40.     }
    41. }
    42. /*反转一个链表*/
    43. ListNode* revList(ListNode* head){
    44.     ListNode* pre=NULL;
    45.     ListNode* cur=head;
    46.     while(cur){
    47.         ListNode* suc=cur->next;
    48.         //操作
    49.         cur->next=pre;
    50.         //更新
    51.         pre=cur;
    52.         cur=suc;
    53.     }
    54.     return pre;
    55. }
    56. int main(){
    57.     int a[]={9,2,44,57,67,123};
    58.     int n=sizeof(a)/sizeof(int);
    59.     ListNode* head=createList(a,n);
    60.     printLink(head);
    61.     ListNode* head2=revList(head);
    62.     printLink(head2);
    63.     deleteNode(head2);
    64. }

    三：删除重复的链表 

     本题要求删除所有重复元素：

    首先建立一个查找表，该查找表只添加不删除

    然后：每遇到一个元素从查找表找，分为查到和没查到两种可能。

    删除一个结点需要用到前驱pre，这里cur的next指针不变，不必设立后继

    • 没查到-----查找表添加该元素，pre指向cur,cur指向下一个
    • 查到了-----新建delNode指向cur以便delete,pre不动，改变next；cur指向下一个
    1. ListNode* deleteDuplicates(ListNode* head) {
    2.          ListNode* pre=NULL;
    3.          ListNode* cur=head;
    4.          set<int> record;
    5.          while(cur){
    6.             if(record.find(cur->val)==record.end()){
    7.                 record.insert(cur->val);
    8.                 pre=cur;
    9.                 cur=cur->next;
    10.             }
    11.             else{
    12.                 ListNode* delNode=cur;
    13.                 pre->next=cur->next;
    14.                 cur=cur->next;
    15.                 delete delNode;
    16.             }
    17.          }
    18.          return head;
    19.     }

    return的是head,因为从头遍历

    四：删除链表的元素 

    法一：

    1.  ListNode* removeElements(ListNode* head, int val) {
    2.         /*
    3.         因为头结点元素的delete改变了头指针head,其他位置head可遍历链
    4.         故而：要考虑待删的是不是头结点
    5.         又因为：可能多个重复值，所以用while
    6.         */
    7.         while(head && head->val==val){
    8.             ListNode* delNode=head;
    9.             head=head->next;//这句话的前提是head不为空
    10.             delete delNode;
    11.         }
    12.         if(head==NULL) return head;
    13.         /*删除需要前驱*/
    14.         ListNode* pre=head;
    15.         ListNode* cur=head->next;
    16.         while(cur){
    17.             if(cur->val==val){
    18.                 ListNode* delNode=cur;
    19.                 pre->next=cur->next;
    20.                 cur=cur->next;
    21.                 delete delNode;
    22.             }
    23.             else{
    24.                 pre=cur;
    25.                 cur=cur->next;
    26.             }
    27.         }
    28.         return head;
    29.     }

    注意几个细节：

    首先删除头结点就是待删元素是，为了避免多次出现用while

    比如：3->3->3->4->5->6->6,删除元素3,得多次

    其次由于cur指向了head->next,为了避免NULL->next,必须if判断。

    最后：元素是待删元素，元素不是待删元素两种情况，必须if-else

    这里可以不使用前驱pre

    1.  ListNode* removeElements(ListNode* head, int val) {
    2.         while(head && head->val==val){
    3.             ListNode* delNode=head;
    4.             head=head->next;//这句话的前提是head不为空
    5.             delete delNode;
    6.         }
    7.         if(head==NULL) return head;
    8.         //判断当前元素下一个元素，自己作为前驱
    9.         ListNode* cur=head;
    10.         while(cur->next){
    11.             if(cur->next->val==val){
    12.                 ListNode* delNode=cur->next;
    13.                 cur->next=delNode->next;
    14.                 delete delNode;
    15.             }
    16.             else{
    17.                 cur=cur->next;
    18.             }
    19.         }
    20.         return head;
    21.     }

    法二：设立虚拟头结点

    1.  ListNode* removeElements(ListNode* head, int val) {
    2.         ListNode* dummyHead=new ListNode(0);//虚拟头结点
    3.         dummyHead->next=head;//虚拟头结点指向真正的head
    4.         ListNode* cur=dummyHead;
    5.         while(cur->next){
    6.             if(cur->next->val==val){
    7.                 ListNode* delNode=cur->next;
    8.                 cur->next=delNode->next;
    9.                 delete delNode;
    10.             }
    11.             else{
    12.                 cur=cur->next;
    13.             }
    14.         }
    15.         ListNode* retHead=dummyHead->next;
    16.         delete dummyHead;
    17.         return retHead;//真正返回的是虚拟头结点前一个
    18.     }

    很简单，创建一个头结点，让其next指向真正的头结点head

    然后两种情况合二为一，因为如果将虚拟结点视为头结点，删除元素一定属于第二种

    最后返回该节点的next指针即可，但是因为要delete,记录一下。

    以链表 1->2->3-null 为例子，删除值为 3 的节点 

     

     

     

     

     

     

     

     

    首先看一下下面的程序：

    1. LinkNode* simpleRec(LinkNode* head) 
    2.     {
    3.         if(head==NULL) return head;//递归结束条件
    4.         LinkNode* pre;
    5.         pre=removeElements(head->next);
    6.         head->next=pre;//把结点链入
    7.         //test---pre的值
    8.         if(pre) cout<<"pre is "<val<
    9.         else cout<<"pre is null"<
    10.         printLink(head);//测试当前链
    11.         cout<
    12.         return head;
    13.     }

    运行结果：

     发现还是递归的思想

    每次因为pre，把链表不断通过head=head- 

    1.  ListNode* removeElements(ListNode* head, int val) {
    2.          //递归结束条件
    3.         if(head==NULL) return NULL;
    4.         //递归子链
    5.         ListNode* res=removeElements(head->next,val);
    6.         //对结果进行选择
    7.         if(head->val==val){
    8.             //不要head,取子链
    9.             return res;
    10.         }
    11.         else{
    12.             //要head,链入子链
    13.             head->next=res;
    14.             return head;
    15.         }
    16.     }

     进一步简化

    1.  ListNode* removeElements(ListNode* head, int val) {
    2.          //递归结束条件
    3.         if(head==NULL) return head;
    4.         //递归子链
    5.         head->next=removeElements(head->next,val);
    6.         //对结果进行选择
    7.         return head->val==val?head->next:head;
    8.     }

    把res这个变量直接作为：head->next的子链

    可以把这个递归思路沿用到--删除重复元素

    1.   ListNode* deleteDuplicates(ListNode* head) {
    2.          if(head==NULL) return head;
    3.          set<int> record;
    4.          head->next=deleteDuplicates(head->next);
    5.          if(head->next) record.insert(head->next->val);
    6.          if(record.find(head->val)==record.end()){
    7.              return head;
    8.          }
    9.          else{
    10.              return head->next;
    11.          }
    12.     }

    五： 两两交换链表节点 

    复杂的穿针引线： Swap Nodes in Pairs

    其实不难：

    关键要分析好需要那些节点指针

    既然要交换肯定需要指向两个节点指针：node1和node2

    而且为了成链，需要知道待交换的两个结点的前一个指针p和后一个指针q.

    为了避免头结点的情况讨论，设立虚拟头结点dummyHead

     最后更新一下p的位置即可

    1. ListNode* swapPairs(ListNode* head) {
    2.         //创建虚拟头结点
    3.         ListNode* dummyHead=new ListNode(0);
    4.         dummyHead->next=head;
    5.         ListNode* p=dummyHead;
    6.         /*交换的前提，两个结点均存在*/
    7.         while(p->next&&p->next->next){
    8.             //定义两个结点+后继
    9.              ListNode* node1=p->next;
    10.              ListNode* node2=p->next->next;
    11.              ListNode* q=node2->next;
    12.             //交换节点
    13.             node2->next=node1;
    14.             node1->next=q;
    15.             p->next=node2;
    16.             //更新
    17.             p=node1;//细节---交换后，node1指向了较后面的结点
    18.         }
    19.         //返回结果，释放头结点
    20.         ListNode* res=dummyHead->next;
    21.         delete dummyHead;
    22.         return res;
    23.     }

     六：删除结点

    不仅仅是穿针引线 

     

     void deleteNode(ListNode* node) {}

    1.  void deleteNode(ListNode* node) {
    2.         if(node==NULL) return;
    3.         if(node->next==NULL){
    4.             delete node;
    5.             node=NULL;
    6.             return;
    7.         }
    8.         node->val=node->next->val;
    9.         ListNode* delNode=node->next;
    10.         node->next=delNode->next;
    11.         delete delNode;
    12.     }

    把待删结点用其后一个结点赋值，删除后一个结点即可

    这里是改变链表的某一个值来达到目的

    七：删除链表倒数第n个结点

     只遍历一遍链表，不从链表长度入手

    思路：

    因为要删第n个，需要找到它的前一个结点。不妨让指针p，q之间距离为n+1.

    p从头遍历，p,q每次都移动一步（相同距离），最后q==NULL,p就恰好指向待删结点前驱

     

     

    1. ListNode* removeNthFromEnd(ListNode* head, int n) {
    2.         assert(n>=0);
    3.           ListNode* dummyHead=new ListNode(0);
    4.           dummyHead->next=head;
    5.           //定义双指针
    6.           ListNode* p=dummyHead;
    7.           ListNode* q=dummyHead;
    8.           //设定p,q距离为n+1
    9.           for(int i=0;i1;i++){
    10.               assert(q);
    11.               q=q->next;
    12.           }
    13.           while(q){
    14.               p=p->next;
    15.               q=q->next;
    16.           }
    17.           //删除
    18.           ListNode* delNode=p->next;
    19.           p->next=delNode->next;
    20.           delete delNode;
    21.           //返回
    22.           ListNode* res=dummyHead->next;
    23.           delete dummyHead;
    24.           return res;
    25.     }

  • 相关阅读:
    单元测试的重要性
    京东API接口解析，实现获得JD商品评论
    python排序算法（六）、希尔排序
    Ubuntu中查看电脑有多少个核——lscpu
    哈希(Hash)
    【Qt之QString】数值与进制字符串间的转换详解
    docker 安装oracle 19c
    一些自己收集的秒杀设计的重要知识点
    JAVA的File对象
    AWD学习总结 （会持续更新）
  • 原文地址：https://blog.csdn.net/weixin_47173597/article/details/126840204