精华内容
下载资源
问答
  • 合并两个有序链表(java)

    千次阅读 2019-07-29 17:55:43
    输入两个单调递增链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 想法☁: 1.题目告诉两个链表,那你首先应想到,如果给你的两个链表的其中一个是空的,则返回另外一个链表节点头...

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

    想法☁:
    1.题目告诉两个链表,那你首先应想到,如果给你的两个链表的其中一个是空的,则返回另外一个链表节点头就好了。
    2.新定义一个链表的头节点,该结点就是要返回的结点哦。
    3.定义三个指针,用来跑链表。
    4.如果整个循环跳出,则表示其中一个链表为空,则把新链表尾节点的next域设置为不为空链表的指针就?了。

    /*
    class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1 == null)
                return list2;
            if(list2 == null)
                return list1;
            //跑list1的指针
            ListNode p = list1;
            //跑list2的指针
            ListNode q = list2;
            //确定新链表的头结点
            ListNode newList = (p.val < q.val)? p : q;
            //跑新链表的指针
            ListNode s = newList;
            if(newList == q)
                q = q.next;
            else
                p = p.next;
            while(p != null && q != null){
                if(p.val < q.val){
                    s.next = p;
                    s = p;
                    p = p.next;
                }else{
                    s.next = q;
                    s = q;
                    q = q.next;
                }
            }
            //把不为空的 p/q 直接挂在 s.next 上
            if(p != null)
                s.next = p;
            else
                s.next = q;
            return newList;
    
        }
    }

    递归思想⭕
    每次合并之前都要比较两个链表的头节点值的大小,故能通过递归去做这个题。

    public class Solution {
        public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1 == null)
                return list2;
            if(list2 == null)
                return list1;
            ListNode newHead = null;
            if(list1.val < list2.val){
                newHead = list1;
                //看清楚递归进去是确定 newHead.next 的值!!!
                newHead.next = Merge(list1.next,list2);
            }else{
                newHead = list2;
                newHead.next = Merge(list1,list2.next);
            }
            return newHead;
        }
    }
    展开全文
  • 输入两个单调递增链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 public class Solution { public static void main(String[] args) { // 创建两个链表 // 第一个链表: 1->...

    输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

    public class Solution {
    	public static void main(String[] args) { 
    		// 创建两个链表 // 第一个链表: 1-> 2 -> 4 
    		ListNode l1 = new ListNode(1); 
    		// 这是第一个链表的第一个节点(不能用这个节点去往下加数据)
    		// 必须有一个指针去往第一个节点上去加数据 
    		ListNode p1 = l1; 
    		// 这个指针节点会从链表的第一个节点一直往下走(直至最后一个节点) 
    		p1.next = new ListNode(2); 
    		p1 = p1.next; 
    		p1.next = new ListNode(4); 
    		System.out.println(l1.val);
    		// 第二个链表     1-> 3 -> 4
    		ListNode l2 = new ListNode(1); 
    		ListNode p2 = l2; 
    		p2.next = new ListNode(3); 
    		p2 = p2.next; 
    		p2.next = new ListNode(4); 
    		System.out.println(l2.val);
    		Solution s = new Solution();
    		System.out.println(s.mergeTwoLists(l1, l2));
    		}
    		
    	public ListNode mergeTwoLists(ListNode l1, ListNode l2){
    		ListNode p1 = l1;
    		ListNode p2 = l2;
    		ListNode l3Head ;
    		if(p1==null){
    			return p2;
    		}
    		if(p2==null){
    			return p1;
    		}
    		if(p1.val<p2.val){
    			l3Head = new ListNode(p1.val);
    			p1 = p1.next;
    		}else{
    			l3Head = new ListNode(p2.val);
    			p2 = p2.next;
    		}
    		ListNode curr = l3Head;
    		while(p1!=null && p2!=null){
    			if(p1.val==p2.val){
    				curr.next = new ListNode(p1.val);
    				curr = curr.next;
    				curr.next = new ListNode(p2.val);
    				curr = curr.next;
    				p1 = p1.next;
    		        p2 = p2.next;
    			}
    			else if(p1.val<p2.val){
    				curr.next = new ListNode(p1.val);
    				p1 = p1.next;
    				curr = curr.next;
    			}else{
    				curr.next = new ListNode(p2.val);
    				p2 = p2.next;
    				curr = curr.next;
    			}
    		}
    		if (p1 != null) {
    			curr.next = p1;
    		}
    		if (p2 != null) {
    			curr.next = p2;
    		}
    		return l3Head;
    	}
    }
    
    

     

    展开全文
  • 1 /*将两个有序递增链表合并成一个有序递增链表,要求结果仍使用原来两个链表的存储空间,不另外占有空间。*/ 2 #include<stdio.h> 3 #include<stdlib.h> 4 #define MAXSIZE 20; 5 typedef ...

    完整程序:

    /*将两个有序递增链表合并成一个有序递增链表,要求结果仍使用原来两个链表的存储空间,不另外占有空间。*/
    #include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 20;
    typedef struct LNode{
        int data;
        struct LNode *next;
    } LNode,*LinkList;
    LinkList mergelinklist(LinkList La,LinkList Lb){
    //已知链表La,Lb的元素按递增排序。
    //将两链表合并,仍然使用La的表头,将两个表比较,依次将存储空间连到La上。
    //要合并后的链表仍然是递增的,需要尾插法。
        LinkList pa,pb;   //定义两个指针又来存储La,lb从首元结点开始向后的链表
        pa=La->next;     //La链表已经赋值给了pa,这样就可以使用La的头结点,作为新链表的头结点。
        pb=Lb->next;    
        free(Lb);       //Lb从首元结点开始已经赋值给了pb,所以把Lb,的头结点释放。
        LinkList last=La;      //last存储尾结点的地址。
        while(pa&&pb){
            if(pa->data<pb->data)
            {
                LinkList p=pa->next;  //先把pa的下一个结点地址存储下来。
                pa->next=NULL;        //用尾插法将pa当前结点插入La。
                last->next=pa;    
                last=last->next;
                pa=p;                //pa后移一位。
            }
            else if(pa->data==pb->data){  //值相等的情况
                LinkList p=pa->next;      //将pa当前结点插入La.
                pa->next=NULL;     
                last->next=pa;
                last=last->next; 
                pa=p;             //pa后移一位
                LinkList q=pb;
                pb=pb->next;        //释放当前结点,并且后移一位
                free(q);
            }
            else{
                LinkList p=pb->next;  //指向pb后一个结点 
                pb->next=NULL;     //把pb结点的next置空 
                last->next=pb;    //此时pb中的元素比pa中的小,应把pb链接到pa的前面 
                last=last->next;   //把last指针后移,保持last一直指向最后一个结点 
                pb=p;              //pb后移一位,对下一个结点元素进行与pa的比较 
            }
        }
        last->next=pa?pa:pb;   //pa,pb哪一个链表还没完,就将它连接到La后面。
        return La;
    }
    int main(){
        LinkList La,Lb;
        int n,m,i;
        La=(LinkList)malloc(sizeof(LNode));
        La->next=NULL;
        Lb=(LinkList)malloc(sizeof(LNode));
        Lb->next=NULL;
        LinkList last=La;
        printf("请输入第一个有序递增表的长度:");
        scanf("%d",&n);
        printf("\n");
    	printf("请输入第一个有序递增表的元素:"); 
        for(i=0;i<n;i++)
        {
            LinkList p;
            p=(LinkList)malloc(sizeof(LNode));
            scanf("%d",&p->data);
            p->next=NULL;
            last->next=p;
            last=last->next;
        }
        last=Lb;
        printf("\n");
        printf("请输入第二个有序递增表的长度:");
        scanf("%d",&m);
    	printf("\n");
    	printf("请输入第二个有序递增表的元素:");   
        for(i=0;i<m;i++)
        {
            LinkList p;
            p=(LinkList)malloc(sizeof(LNode));
            scanf("%d",&p->data);
            p->next=NULL;
            last->next=p;
            last=last->next;
        }
        printf("\n");
        La=mergelinklist(La,Lb);
        LinkList p=La;
        p=p->next;
        printf("合并后的有序表为:"); 
        while(p){
            printf("%d   ",p->data);
            p=p->next;
        }
        printf("\n");
        return 0;   
    }
    

    解析图:

     
    展开全文
  • } //将两个递增有序链表合并为一个递增有序链表 public void mergeSurgeList(LinkList La) { if (La==null) { System.out.println("Error"); return ; } if(!isSurge(La)) { System.out.println("No surge"); ...

    代码如下:

    package sjjgniub;
    
    import java.util.LinkedList;
    import java.util.Scanner;
    
    @SuppressWarnings("all")
    public class LinkList {
    
        private class Node
        {
            int data;
            Node next;
    
            public Node()
            {
    
            }
    
            public Node(int data)
            {
                this.data = data;
                next = null;
            }
        }
    
        Node head = null;
    
        public LinkList(){
            head = new Node();
            if (head==null)
            {
                System.out.println("Error");
                return;
            }
            head.next = null;
        }
    
        public void createList(int[] arr)
        {
            Node p = head;
            for (int i = 0;i<arr.length;i++) {
                Node s = new Node(arr[i]);
                p.next = s;
                p = s;
            }
        }
    
        public void createList()
        {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            Node p = head;
            for (int i = 0;i<n;i++)
            {
                int temp = sc.nextInt();
                Node s = new Node(temp);
                p.next = s;
                p = s;
    
            }
        }
    
        public void printList()
        {
            Node p = head.next;
            while(p!=null)
            {
                System.out.print(p.data+" ");
                p = p.next;
            }
            System.out.println();
        }
    
        //判断是否为递增有序链表
        public boolean isSurge(LinkList L)
        {
    
           if (L==null)
           {
               return false;
           }
           else if (L.head.next==null)
           {
               return true;
           }
           Node p = L.head.next;
           while(p.next!=null)
           {
               if (p.next.data < p.data)
               {
                   return false;
               }
               p = p.next;
           }
           return true;
        }
    
        //将两个递增的有序链表合并为一个递增的有序链表
        public void mergeSurgeList(LinkList La)
        {
            if (La==null)
            {
                System.out.println("Error");
                return ;
            }
    
            if(!isSurge(La))
            {
                System.out.println("No surge");
                return ;
            }
    
            if (!isSurge(this))
            {
                System.out.println("No surge");
                return ;
            }
    
    
    
    
            Node pc = head;
            Node p1 = head.next;
            Node p2 = La.head.next;
            while(p1!=null && p2!=null)
            {
                if (p1.data > p2.data)
                {
                    pc.next = p2;
                    p2 = p2.next;
                    pc = pc.next;
                }
                else if (p1.data < p2.data)
                {
                    pc.next = p1;
                    p1 = p1.next;
                    pc = pc.next;
                }
                else
                {
                    pc.next = p1;
                    p1 = p1.next;
                    p2 = p2.next;
                    pc = pc.next;
                }
            }
            if (p1==null && p2==null)
            {
                pc.next = null;
            }
            else if (p1==null)
            {
                pc.next = p2;
    
            }
            else if (p2==null)
            {
                pc.next = p1;
            }
            La = null;
    
    
        }
    
    
        //将两个非递减的有序链表合并为一个非递增的有序链表
        public void mergeNotSurgeList(LinkList La)
        {
            if (La==null)
            {
                System.out.println("Error");
                return ;
            }
            if(!isSurge(La))
            {
                System.out.println("No surge");
                return ;
            }
    
            if (!isSurge(this))
            {
                System.out.println("No surge");
                return ;
            }
    
            Node pc = head;
            Node p1 = head.next;
            Node p2 = La.head.next;
            pc.next = null;
            while(p1!=null&& p2!=null)
            {
                if (p1.data >= p2.data)
                {
                    Node tmp = p2.next;
                    p2.next = pc.next;
                    pc.next = p2;
                    p2 = tmp;
                }
                else
                {
                    Node tmp = p1.next;
                    p1.next = pc.next;
                    pc.next = p1;
                    p1 = tmp;
                }
            }
    
    	 while(p2!=null)
           {
               Node tmp = p2.next;
               p2.next = pc.next;
               pc.next = p2;
               p2 = tmp;
           }
    
           while(p1!=null)
           {
               Node tmp = p1.next;
               p1.next = pc.next;
               pc.next = p1;
               p1 = tmp;
           }
    
            La = null;
    
        }
    
    }
    
    

    测试类:

    package sjjgniub;
    
    public class TestList {
        public static void main(String[] args) {
            LinkList linkList = new LinkList();
            int[] arr1 = {1,56,234,423,1000};
            linkList.createList(arr1);
            linkList.printList();
            LinkList linkList2 = new LinkList();
            int[] arr2 = {213,423,1000};
            linkList2.createList(arr2);
            linkList2.printList();
            System.out.println();
    
          //  linkList.mergeSurgeList(linkList2);
            linkList.mergeNotSurgeList(linkList2);
            linkList.printList();
        }
    }
    
    
    展开全文
  • 链表1的头结点值小于链表2头结点的值,我们就将链表1作为合并链表的头结点,在剩余结点中,链表2的头结点值小于链表1头结点的值,我们将链表二的头结点作为合并链表的后续结点,且剩余结点依然是有序的,合并的...
  • 该算法为将两个递增链表合并为一个递减链表,采用头插法和尾插法两种不同的方法实现
  • 合并两个有序递增的单链表,使得合并后,新链表也是递增有序的。这里分别使用循环、递归实现合并有序链表 循环实现链表合并和递归实现链表的合并如下所示: package cn.edu.nwu.structs.linklist; /** * @author ...
  • 合并两个有序链表

    2018-07-31 21:27:44
    合并两个有序链表 输入两个单调递增链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 1. 递归版本 根据上面的图得到 , 先创建一个新的结点 , 然后比较两个链表的第一个节点...
  • 两个有序链表合并

    2019-03-14 11:16:17
    两个有序链表合并成一个链表合并后的链表仍然是有序的,依次输出合并后的链表的元素值,并求出第奇数位置元素之和
  • 输入两个单调递增链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 分析: 定义一个新的链表,用来存放合并后的链表,并记录该链表的头结点。 1.判断list1是否为空,如果为空...
  • 分析:意思就是递增链表合并成为一条递减链表,然后还不能重新创建新的链表,要在原有的条链表上修改,要最终的链表逆序,所以使用头插法,将AB条链表的元素进行比较,较小的进行头插,和Day2类似,Day2时...
  • 方法:递归 ... * 两个递增链表合并 * 递归 */ //节点 public static class Node{ int data; Node next = null; public Node(int val) { this.data = val; } } //插入链表 public st...
  • //将两链表合并,仍然使用La的表头,将两个表比较,依次将存储空间连到La上。 //要合并后的链表仍然是递增的,需要尾插法。 LinkList pa,pb; //定义两个指针又来存储La,lb从首元结点开始向后的链表 pa=La->next; /...
  • 题目: 将两个有序链表合并为一个新的有序链表并返回。...4看到这个题,让我想起上次写的博客,合并两个有序的数组。这个题,是链表的合并,这就比较好移动,可以用递归实现链表的拼接所以,代...
  • 合并两个递增有序链表 将两个递增有序链表合并为一个递增有序链表 LNode *Merge(LNode *L1,LNode *L2){ if(L1==0||L2==0) return 0;//若两表为空则返回空 if(L1->next==0) return L2; //表1为空直接返回...
  • 要求结果链表仍使用原来两个链表的存储空间,不另外占用其他的存储空间,表中不允许由重复的数据 #include<iostream> using namespace std; //自定义链表的存储结构 typedef struct LNode { int date; ...
  • 两个升序链表合并为一个新的 升序 链表并返回。 新链表是通过拼接给定的两个链表的所有节点组成的。 例如: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 问题解析 先判断两个...
  • 浅拷贝只复制指针地址,两个对象共用一块内存,更改其中一个值会导致另一个跟着改变,删除可能会造成错误。 void Merge(SingleList* L1, SingleList* L2) //L2接收合并链表 { if (L2->first == NULL) .
  • 合并两个有序链表 题目描述: 输入两个单调递增链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 方案:使用两个指针,比较两个节点的值 代码: class Solution { public: ListNode*...
  • 合并两个有序链表 图解说明

    千次阅读 多人点赞 2020-11-29 12:09:29
    合并两个有序链表 题目描述 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->...
  • ① 我们知道头插法最终创建的链表的顺序与插入的顺序正好是相反的,所以我们可以修改之前的将两个递增有序链表合并成一个非递减的链表程序,将头插法修改为尾插法 ② 与头插法不同的是,头插法在while循环之后...
  • 两个有序链表合并成一个有序链表

    千次阅读 2019-04-17 14:04:04
    算法:两个有序链表合并成一个有序链表(Java实现) 首先我们创建链表的结构类 @Getter @Setter class Node{ private Integer data; //存储数据 private Node next; //后继引用 public Node(Integer data) { ...
  • 代码注释处的两个排序函数有BUG,先放着,等以后看看错在哪里。 第三个排序函数没问题,可正常运行。 #include<iostream> using namespace std; typedef struct LNode { int data; struct LNode* next; int...
  • 输入链表A 与B(空格分隔),说输入的数字序列可以无序 最后合并成一个有序的列表!MFC可视化编程
  • 两个非递增的有序链表合并为一个非递减的有序链表 将两个非递增的有序链表合并为一个非递减的有序链表。...将两个递减链表合并为一个递增链表;使用递归进行合并,迭代方式反转。空间复杂度O(1)
  • 两个递增有序链表合并为一个递增有序链表。要求结果链表仍使用原来两个链表 #include &quot;stdio.h&quot; #include&amp;lt;stdlib.h&amp;gt; typedef struct node{ int data; struct node* ...
  • 合并两个有序链表

    2021-04-28 15:42:29
    1、首先定义一个虚拟头节点node,把两个有序链表节点都插入到node头节点的后面,最后的返回值为node后面的节点node.next 2、再定义一个cur的临时节点,cur指向node的头节点,用cur来记录list1和list2的插入情况,...
  • 合并两个排序的链表 输入两个单调递增链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。 示例1 输入:{1,3,5},{2,4,6} 返回:{1,2,3,4,5,6}解题思路 定义两个指针,指向一条带头...
  • 两个递增有序链表合并为一个递增有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 void MergeList(LinkList &La,LinkList &Lb,LinkList ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,985
精华内容 4,394
关键字:

合并两个有序递增链表