精华内容
下载资源
问答
  • 有序链表合并

    2017-09-17 15:06:19
    有序链表合并: LA、LB是两个带头结点的有序链表,归并两个链表得到新的有序表LC。设立指针pa,pb,pc,其中pa和pb分别指向LA,LB中当前待比较的结点,pc指向LC表中当前最后一个结点。将pa,pb结点中值较小的一个...

    归并排序:
    LA、LB是两个带头结点的有序链表,归并两个链表得到新的有序表LC。设立指针pa,pb,pc,其中pa和pb分别指向LA,LB中当前待比较的结点,pc指向LC表中当前最后一个结点。将pa,pb结点中值较小的一个链接到pc之后。

    typedef struct Node
    {
        int data;
        struct Node* next;
    }Node,*PLink;
    
    //销毁链表
    void DeleteLink(PLink& head)
    {
        while(head)
        {
            PLink delNode = head;
            head = head->next;
            delete delNode;
            delNode = NULL;
        }
    }
    //打印链表
    void PrintLink(PLink head,bool bdel=false)
    {
        if (head == NULL)
        {
            return;
        }
        while(head)
        {
            cout<<head->data<<" ";  
            head= head->next;       
        }
        cout<<endl;
    }
    //合并链表 带头结点
    PLink union_link_h(PLink& La,PLink& Lb)
    {
        //La Lb的元素值按照递增排列
        PLink pa,pb,pc,LC;
        pa = La->next,pb = Lb->next;
        LC = pc = La;   //用La的头结点作为返回链表的头结点
    
        while(pa&&pb)//若pa或pb中有一个为空,则说明该表已经归并完
        {
            if (pa->data < pb->data)
            {
                pc->next = pa;
                pc = pa;
                pa = pa->next;
            }
            else
            {
                pc->next = pb;
                pc = pb;
                pb = pb->next;
            }
        }
        pc->next = pa?pa:pb;    //插入剩余段
        delete Lb;              //释放Lb的头结点
        Lb = NULL;
        return R;
    }
    
    int main()
    {
        PLink la,lb,LA,LB,LR;
        LA =la  = new Node;
        LB = lb = new Node;
    
        for (int i=1;i<10;i++)
        {
            PLink ta,tb;            
            if (i%2)
            {
                ta = new Node;
                ta->data = i;
                la->next = ta;
                la=ta;
            }
            else
            {
                tb = new Node;
                tb->data = i;
                lb->next = tb;
                lb = tb;
            }
        }
        la->next = NULL;
        lb->next = NULL;
    
        PrintLink(LA->next);//LA: 1 3 5 7 9
        PrintLink(LB->next);//LB: 2 4 6 8
        LR = union_link_h(LA,LB);   
        PrintLink(LR->next);
    
        DeleteLink(LR);
        return 0;
    }

    运行结果:

    展开全文
  • C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
  • 两个有序链表合并成一个有序链表

    千次阅读 2019-04-17 14:04:04
    算法:两个有序链表合并成一个有序链表(Java实现) 首先我们创建链表的结构类 @Getter @Setter class Node{ private Integer data; //存储数据 private Node next; //后继引用 public Node(Integer data) { ...

    算法:两个有序链表合并成一个有序链表(Java实现)
    首先我们创建链表的结构类

    @Getter
    @Setter
    class Node{
        private Integer data;   //存储数据
        private Node next;   //后继引用
        public Node(Integer data) {
            this.data = data;
        }
    }
    

    准备数据:

    	//准备第一个有序链表
    Node readyNode1(){
        Node node = new Node(1);
        Node node1 = new Node(6);
        Node node2 = new Node(9);
        Node node3 = new Node(10);
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        return node;
    }
    
    //准备第二个有序链表
    Node readyNode2(){
        Node node = new Node(2);
        Node node1 = new Node(3);
        Node node2 = new Node(8);
        Node node3 = new Node(14);
        Node node4 = new Node(22);
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        return node;
    }
    

    我们想要实现链表的合并排列。
    1.就要新建一个链表;
    2.然后依次比较初始链表的大小;把数值小的放到新链表中,注意:只能放链表的值,不能放后继指针。
    3.每次在新链表中插入数据的时候,都要保证插入的数据是在新链表的最后一个节点上。
    代码如下:

    //合并两个有序链表
    public Node hebing(Node node1, Node node2){
    	 if (node1 == null)   return node2;
         if (node2 == null)   return node1;
        
        Node node3 = null;       //递归合并两个有序链表   
        while(node1 != null || node2 != null) {
            Node n = new Node();    //每次循环使用一个Node去存储数据
            if (node1 == null) {
                getLastNode(node3).next = node2;
                break;
            } else if (node2 == null) {
                getLastNode(node3).next = node1;
                break;
            } else if (node1.data > node2.data) {
                n.data = node2.data;
                node2 = node2.next;
            } else if (node1.data <= node2.data) {
                n.data = node1.data;
                node1 = node1.next;
            }
    
            if (node3 == null) {
                node3 = n;
            } else {
                getLastNode(node3).next = n;
            }
    
        }
        return node3;
    }
    
    /**
     * 获取链表的最后一级
     */
    public Node getLastNode(Node node){
        while (node != null){
            if (node.next == null) {
                return node;
            } else {
                node = node.next;
            }
        }
        return null;
    }
    

    测试

    @Test
    public void run(){
        Node node1 = readyNode1();
        Node node2 = readyNode2();
        Node hebing = hebing(node1, node2);
        System.out.println(JSONObject.toJSONString(hebing));
    }
    

    输出结果:

    		{"data":1,"next":{"data":2,"next":{"data":3,"next":{"data":6,"next":{"data":8,"next":{"data":9,"next":{"data":10,"next":{"data":14,"next":{"data":22}}}}}}}}}
    
    展开全文
  • 多个有序链表合并成一个有序链表的C++递归实现 主体思想: 1.多个有序链表看成是一个二维链表,此二维链表在 y 轴方向是有序的,x轴方向是无序的 2.在x 轴方向(x=0),找出此维度最小的元素(可以输出了), 3....

     多个有序链表合并成一个有序链表的C++递归实现

    主体思想:

    1.多个有序链表看成是一个二维链表,此二维链表在 y 轴方向是有序的,x轴方向是无序的

    2.在x 轴方向(x=0),找出此维度最小的元素(可以输出了),

    3.将此元素置于x 轴最大的地方,重新将 y=x 的这一条有序链表 沿 y 轴方向移动 -1 (当此链表没有元素 存在 y>= 0了,删除此一维链表).

    4.重复在 x=0 这一层找到最小的元素,重复 3、4 。(可以递归了)

    手动图片讲述,小节点内有数字,1是初始状态,2\3循环,(2的过程在 FindMin() 中,图片简化过程)

    注意:

    1.递归的判断条件  --  二维链表是否为空

    2.初始化 vector 的时候,请注意不要仅初始化 vector <ListNode*> *   , 这个是仅初始化了一个指针,并没有初始化 vector ,我花了很久来调这个较低级的错误。

    3.创建基础数据的时候(create()),即二维链表,注意别打错字,链表出了循环,将会溢栈,很莫名也不好找的错误。

    // MergeList.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<vector>
    
    using namespace std;
    
    typedef struct ListNode {
    	int item;
    	struct ListNode * next = NULL;
    };
    
    class MergeList
    {
    
    public:
    	//lists 直接记录每一个链表第一个节点
    	bool mergeKLists(vector<ListNode*>* lists, ListNode * mergeHead)//使用vector<ListNode*>地址,可以直接对vector进行修改
    	{
    		if (lists->size() == 0) //List 中一个元素都没了,排序结束
    			return false;	
    
    		mergeHead->next = FindMin(lists); //mergeHead 记录最小值
    		lists->pop_back(); //先删除最小的一个
    
    		//如果list 中最小的一个 元素不是这个链表中的尾节点,再在链表最末端加上其下一个元素地址,即 mergeHead->next->next
    		if (mergeHead->next->next != NULL) 
    			lists->push_back(mergeHead->next->next);
    
    		//在mergeHead 添加完一个元素后,继续寻找下一个元素
    		mergeKLists(lists, mergeHead->next);
    
    		return false;
    	}
    
    private:
    	//优化冒泡,返回最小的节点,进行添加(链表排序用归并,代码较多,太繁琐了),并把最小节点放到vector末尾。
    	ListNode * FindMin(vector<ListNode*>* lists)
    	{
    		int num = lists->size();
    		for (int i = 0; i < num - 1; i++)//数组下标
    		{
    			if (lists->at(i)->item < lists->at(i + 1)->item)
    				swap(lists->at(i), lists->at(i + 1)); //小的沉底
    		}
    		return lists->at(num-1);
    	}
    
    	
    };
    //创建测试数据
    void create(vector<ListNode *> * lists);
    
    int main()
    {
    	ListNode * mergeHead = new ListNode;  mergeHead->item = -1;
    	vector<ListNode *> LLists;
    	MergeList mergeList ;
    
    	//创建二维链表
    	create(&LLists);
    	//进行多链表合并
    	mergeList.mergeKLists(&LLists, mergeHead);
    	
    	//输出打印链表
    		while (mergeHead->next != NULL)
    		{
    			mergeHead = mergeHead->next;
    			cout << mergeHead->item << endl;
    		}
    
    		getchar();
    	return 0;
    }
    
    void create (vector<ListNode *> * lists)
    {
    	ListNode *a1, *a2, *a3, *a4, *a5;
    	ListNode *b1, *b2, *b3;
    	ListNode *c1, *c2, *c3, *c4;
    	ListNode *d1, *d2, *d3;
    	ListNode *e1, *e2, *e3, *e4;
    
    	//创建链表 a1
    	a5 = new ListNode;
    	a5->item = 87; a5->next = NULL;
    	a4 = new ListNode;
    	a4->item = 46; a4->next = a5;
    	a3 = new ListNode;
    	a3->item = 39; a3->next = a4;
    	a2 = new ListNode;
    	a2->item = 28; a2->next = a3;
    	a1 = new ListNode;
    	a1->item = 1; a1->next = a2;
    
    	//创建链表 b1
    	b3 = new ListNode;
    	b3->item = 10; b3->next = NULL;
    	b2 = new ListNode;
    	b2->item = 7; b2->next = b3;
    	b1 = new ListNode;
    	b1->item = 2; b1->next = b2;
    
    	//创建链表 c1
    	c4 = new ListNode;
    	c4->item = 28; c4->next = NULL;
    	c3 = new ListNode;
    	c3->item = 19; c3->next = c4;
    	c2 = new ListNode;
    	c2->item = 8; c2->next = c3;
    	c1 = new ListNode;
    	c1->item = 6; c1->next = c2;
    
    	//创建链表 d1
    	d3 = new ListNode;
    	d3->item = 80; d3->next = NULL;
    	d2 = new ListNode;
    	d2->item = 27; d2->next = d3;
    	d1 = new ListNode;
    	d1->item = 4; d1->next = d2;
    
    	//创建链表 e1
    	e4 = new ListNode;
    	e4->item = 60; e4->next = NULL;
    	e3 = new ListNode;
    	e3->item = 47; e3->next = e4;
    	e2 = new ListNode;
    	e2->item = 42; e2->next = e3;
    	e1 = new ListNode;
    	e1->item = 37; e1->next = e2;
    
    	lists->push_back(a1);
    	lists->push_back(b1);
    	lists->push_back(c1);
    	lists->push_back(d1);
    	lists->push_back(e1);
    }

    代码运行结果截图:

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

    """
    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

    示例:

    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4

    """

    链表结构:

    class ListNode():
        def __init__(self, x):
            self.val = x
            self.next = None
    class Solution:
        # 方法一 :
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            head = ListNode(None)
            l3 = head
            while l1 and l2 :
                if l1.val < l2.val:
                    # 重点: 时刻保持下一个 .next 结构是一个 ListNode
                    l3.next = ListNode(l1.val)
                    l1 = l1.next
                else:
                    l3.next = ListNode(l2.val)
                    l2 = l2.next
                l3 = l3.next
            if l1 == None:
                while l2:
                    l3.next = ListNode(l2.val)
                    l3 = l3.next
                    l2 = l2.next
            else:
                while l1:
                    l3.next = ListNode(l1.val)
                    l3 = l3.next
                    l1 = l1.next
            return head.next

     

       # 方法 二
       def mergeTwoLists2(self, l1: ListNode, l2: ListNode) -> ListNode:
            # 递归解法
            if not l1: return l2
            if not l2: return l1
            if l1.val < l2.val:
                l1.next = self.mergeTwoLists(l1.next, l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1, l2.next)
                return l2

    验证,设置输入、输出:

    if __name__ == "__main__":
        s = Solution()
        #输入:    1->2->4
        #          1->3->4
        # 输出:1->1->2->3->4->4
        l1 = ListNode(1)
        tmp = ListNode(2)
        l1.next = tmp
        tmp.next = ListNode(4)
        l2 = ListNode(1)
        tmp = ListNode(3)
        l2.next = tmp
        tmp.next = ListNode(4)
        r = s.mergeTwoLists2(l1,l2)
        print(r.val)
        # 先判断是否为 None , 再去打印
        while r.next != None:
            r = r.next
            print(r.val)

     

    展开全文
  • Description将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。示例:输入:1->2->4, 1->3->4输出:1->1->2->3->4->4Analyze给定的函数...
  • 将两个非递增的有序链表合并为一个非递减的有序链表 将两个非递增的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。操作的名称...
  • 将两个有序链表合并为一个有序链表 思路: 1.必须保证两个链表为有序链表 2.在两个链表都不为空的条件下,设一个 last=null; (1)如果链表1的值小于等于链表2的值,进行循环,先放链表1的值到新链表result,...
  • 将两个有序链表合并成一个有序链表 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef struct _node{ int number; struct _node *next; }Node; typedef struct{ Node *head;...
  • 利用递归法将两有序链表合并成链表,且合并后的链表仍然有序。 比较链表1和链表2的第一个结点数据,如果head1.data&lt;head2.data,则把结果链表头指向链表1的第一个结点。 对剩余的head1.next和链表2再次递归...
  • java中将两个有序链表合并为一个有序链表: 1.必须保证两个链表为有序链表 2.在两个链表都不为空的条件下,设一个 last=null; (1)如果链表1的值小于等于链表2的值,进行循环,先放链表1的值到新链表result,...
  • 将两个有序链表重新排序,合并为一个新...//将两个有序链表合并为一个新的有序链表并返回 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { //链表是否1为null return l2; } el...
  • 两个有序链表合并 链表插入 删除 修改等
  • 将两个有序链表合并,合并后的链表仍为有序链表 思路分析: 1)首先定义一个新的链表,并且将其初始化,再定义一个辅助节点cur,该节点指向新的链表的头节点mergeHead 2)循环遍历两个链表h1,h2,每次遍历时各取出一...
  • 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 2.解法 /** * Definition for singly-linked list. * public class ListNode { * int val; * ...
  • 将两个有序链表合并成一个链表

    万次阅读 多人点赞 2018-08-04 17:05:37
    代码实现功能如下:将两个有序链表合并成一个有序链表。 具体思路如下:首先自己调用链表的创建函数,手动创建两个有序链表,链表的创建以输入0作为截止标志。创建好两个有序链表之后,将两个链表的头结点进行比较...
  • 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 void MergeList(LinkList &La,LinkList &Lb,LinkList ...
  • 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 /** * Definition for ...
  • C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现 /*! * Copyright (c) 2020,ZYF. * All Rights Reserved. * * \file MergerListNode.cpp * \brief C++版本将两个有序链表合并为一个新的有序链表并...
  • 请实现一个函数,把两个从大到小的有序链表合并成一个链表,新的链表是一个从小到大的有序链表。 struct list { int value; list* next; }; list * merge (list *list1_head, list*list2_head); 代码 list *...
  • 将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 void MergeList(LinkList& La, LinkList& Lb, ...
  • 两个以及K个有序链表合并LeetCode21. 合并两个有序链表(难度:简单)LeetCode23. 合并K个有序链表(难度:困难) LeetCode21. 合并两个有序链表(难度:简单) 将两个升序链表合并为一个新的升序链表并返回。新链表...
  • 有如下两个有序链表str1和str22.合并后的新链表的头结点定义为newpHead,采用摘结点法:三、代码实现(c语言)sListNode*MergeList(sListNode*FirpHead,sListNode*SecpHead){if(FirpHead==NULL){returnSecpHead;}if(S....
  • 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表 #include &quot;stdio.h&quot; #include&amp;lt;stdlib.h&amp;gt; typedef struct node{ int data; struct node* ...
  • 有序链表合并
  • C++有序链表合并

    2015-08-08 10:28:32
    将两个有序链表合并成一个新的有序链表,例:  list1: 1->4->8->9  list2: 2->3->5->6->10 合并后  list: 1->2->3->4->5->6->8->9->10 分析 利用两指针p1,p2分别指向两链表的头head1,head2,依次比较...
  • 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表约存储空间。表中不允许有重复的数据。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,281
精华内容 18,112
关键字:

有序链表合并