合并两个递增有序的单循环链表

朴灿烈づ我的快乐病毒、 2022-12-11 13:38 140阅读 0赞

## 合并两个递增有序的单循环链表 ##

\**本题要求实现一个合并函数，实现对有序单循环链表tail1和tail2的合并，要求合并时实现去重操作，即合并后的链表中没有重复的元素，并且合并后的链表为递增有序链表。* \*  
1.创建结构体和宏定义类型名。代码如下

#include<stdio.h>
    #include<stdlib.h>
    
    typedef int DataType; 
    struct Node { 
      DataType	  data; 
      struct Node*  next;  
    };
    typedef struct Node  *PNode;    
    typedef struct Node  *LinkList;   
    
    2.创建尾节点，给尾节点的赋值-1.代码入下
    
    ```c
    PNode createEmptyLinkedList()
    { 
      PNode current;
      current = (PNode)malloc(sizeof(Node));
      current->next = NULL;
      current->data = -1;
      return current;
    }

3.创建单循环链表，注意，尾节点并未插入链表中，tail->next指向最后一个节点，并不是tail指向最后一个节点。tail->data的值为-1。代码如下

PNode buildCircularLinkedList(int n, PNode tail)
    { 
    	PNode current=NULL, prev;
    	prev = tail; 
    	for (int i = 0; i < n; i++)
    	{ 
    		current = (PNode)malloc(sizeof(Node));
    		current->next = NULL;
    		scanf("%d", &current->data);
    		prev->next = current;
    		prev = current;
    	}
    	current->next = tail->next;
    	tail->next = current;
    	return tail;
    }

4.实现有序单循环链表tail1和tail2的合并，要求合并时实现去重操作，即合并后的链表中没有重复的元素，并且合并后的链表为递增有序链表。代码如下

PNode mergeNDeduplicateList(PNode tail1, PNode tail2)
    { 
        int temp;
        PNode pre,q;
        //合并tail1和tail2链表，并使此链拆成单向链表，代码如下
        LinkList head=tail1->next->next;      
        tail1->next->next=tail2->next->next;  
        tail2->next->next=NULL;
        //通过指针pre和p的移动，对链表进行冒泡排序
        //小的在前，大的在后，代码如下
        pre=head;  
        q=head->next;
        for(pre=head;pre->next!=NULL;pre=pre->next)
            for(q=pre->next;q!=NULL;q=q->next)
                { 
                    if(pre->data>q->data)
                    { 
                        temp=pre->data;
                        pre->data=q->data;
                        q->data=temp;
                    }
                }
         //对链表进行去重操作，代码如下
         pre=head;
         q=pre->next;
         while(q!=NULL)
         { 
             if(pre->data==q->data)
             {  
                 if(q==tail2->next)  //当最后两个元素相等时，需要做特殊处理
                 { 
                    tail2->next=pre; //因为q->next=NULL,当执行pre->next=q->next时
                     pre->next=NULL; //pre->next=NULL,tail2节点会丢失，不便于
                 }                   //等会链表首尾结合和返回tail2指针 
                  else
                  { 
    
                     pre->next=q->next;
                    free(q);
                    q=pre->next;
    
                  }
             }
             else
             { 
                 pre=q;
                 q=q->next;
             }
         }
         tail2->next->next=head;  //对链表进行首尾接合,并使tail2作为尾指针
         return tail2;
    }

5.打印链表。函数如下

void printCircularLinkedList(PNode tail)
    { 
    
    	PNode current, last;
    	last = tail->next;
    	current = last->next;
    	do
    	{ 
    		printf("%d ", current->data);
    		current = current->next;
    	} while (current != last->next);
    }

6.将函数整合进主函数中。代码如下

int main()
    { 
    	PNode list1, list2;
    	int list1_number, list2_number;
    	list1 = createEmptyLinkedList();
    	list2 = createEmptyLinkedList();
    	scanf("%d", &list1_number);
    	buildCircularLinkedList(list1_number, list1);
    	scanf("%d", &list2_number);
    	buildCircularLinkedList(list2_number, list2);
    	list1 = mergeNDeduplicateList(list1, list2);
    	printCircularLinkedList(list1);
    	return 0;
    }

7.输入样例和输出样例如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNzk4Mzg0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/0e493ff7c16545e08c66e85cbc522534.png

发表评论取消回复

表情：

评论列表（有 0 条评论，140人围观）

还没有评论，来说两句吧...

相关阅读

相关合并两个有序单链表——java实现

题目：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 ![在这里插入图片描述][5482e735460645a8b1

矫情吗；*/ 2024年03月17日 10:31/ 0 赞/ 40 阅读

相关合并两个有序链表

一思路按老师上课讲的，先用其他链表记录两个链表共有部分，然后判断谁null，再接上另一个二代码 class Solution(object):

爱被打了一巴掌/ 2023年07月13日 10:51/ 0 赞/ 28 阅读

相关合并两个有序的单链表，合并之后的新链表依然有序

package com.zzb.datastructure.singlelist; import java.io.Serializable;

忘是亡心i/ 2023年06月30日 09:06/ 0 赞/ 28 阅读

相关合并两个有序链表

class Node { Node next = null;//下一个结点 int data;//结点数据 p

梦里梦外;/ 2023年06月08日 03:19/ 0 赞/ 16 阅读

相关合并两个有序链表

合并两个有序链表 1、题目题目要求：将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例：输

灰太狼/ 2023年03月01日 12:52/ 0 赞/ 27 阅读

相关合并两个递增有序的单循环链表

合并两个递增有序的单循环链表 \本题要求实现一个合并函数，实现对有序单循环链表tail1和tail2的合并，要求合并时实现去重操作，即合并后的链表中没有重复的元素，并且合

朴灿烈づ我的快乐病毒、/ 2022年12月11日 13:38/ 0 赞/ 141 阅读

相关合并两个有序单链表

[https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=13&rp=1&ru=%2Ft

我会带着你远行/ 2022年11月30日 04:18/ 0 赞/ 198 阅读

相关合并两个有序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

向右看齐/ 2022年09月01日 12:56/ 0 赞/ 249 阅读

相关两个有序链表的合并

对于两个有序链表的合并问题，在《剑指offer》中，采用的是如下递归的方式完成的，即： listNode merge(listNode pHead1, listNod

柔情只为你懂/ 2022年08月09日 11:53/ 0 赞/ 188 阅读

相关合并两个有序链表

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

我会带着你远行/ 2021年10月30日 08:20/ 0 赞/ 363 阅读