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

    2020-09-18 21:29:08
    合并有序链表 题目描述 将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的。 代码 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * }...

    合并有序链表

    题目描述

    将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的。

    代码

    import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        /**
         * 
         * @param l1 ListNode类 
         * @param l2 ListNode类 
         * @return ListNode类
         */
        public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
            // write code here
            if(l1 == null){
                return l2;
            }else if(l2 == null){
                return l1;
            }
            if(l1.val < l2.val){
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
            
        }
    }
    
    展开全文
  • 1.合并有序链表 class Node{ int val; Node next=null; Node(int val){ this.val=val; this.next=next; } } //合并有序链表,难点:尾插 //思路:两个链表中的结点,进行结点值的比较,然后将值小的结点尾插...

    1.合并有序链表

    class  Node{
    	int  val;
    	Node  next=null;
    	Node(int  val){
    		this.val=val;
    		this.next=next;
    	}
    }
    //合并有序链表,难点:尾插
    //思路:两个链表中的结点,进行结点值的比较,然后将值小的结点尾插到新链表上,再把剩余链表接到新链表后边
    /*尾插
          分情况:1.链表为空
    	          2.链表不为空
    */
    public  class  MergeTwoLists{
    	public   static  Node mergeTwoLists(Node  head1,Node  head2){
    		if(head1==null){
    			return head2;
    		}
    		if(head2==null){
    			return head1;
    		}
    		if(head1<=head2){
    			head1.next=mergeTwoLists(head1.next,haed2);
    			return head1;
    		}else{
    			head2.next=mergeTwoLists(head1,head2.next);
    			return haed2;
    		}
    	}
    	public  static  Node  mergeTwoLists2(Node  haed1,Node  haed2){
    		if(haed1==null){
    			return haed2;
    		}
    		if(head2==null){
    			return head1;
    		}
    		Node  result=null;//尾插需要一个新链表
    		Node  last=null;
    		Node  cur1=head1;
    		Node  cur2=head2;
    		while(cur!=null&&cur2!=null){//遍历过程中只要两个链表还有值就继续往下走
    			if(cur1.val<=cur2.val){
    				Node  next=cur1.next;
    				if(result==null){
    					result.next=cur1;
    				}else{
    					last.next=cur1;
    				}
    				last=cur1;
    				cur1=next;
    			}
    			else{//走到这里说明cur.val>cur1.val
    				Node  next=cur2.next;
    				if(result==null){
    					result.next=cur2;
    				}else{
    					last.next=cur2;
    				}
    				last=cur2;
    				cur2=next;
    			}
    			if(cur1==null){
    				last.next=cur2;
    			}
    			else{
    				last.next=cur1;
    			}
    			return result;
    		}
    	}
    	public  static  Node  mergeTwoLists3(Node  haed1,Node  haed2){
    		Node  cur1=head1;
    		Node  cur2=head2;
    		Node  result=new  Node();
    		Node last=result;
    		while(cur1!=null&&cur2!=null){
    			if(cur1.val<=cur2.val){
    				last.next=cur1;
    				cur1=cur1.next;
    			}else
    			{
    				last.next=cur2;
    				cur2=cur.next;
    			}
    			last=last.next;
    		}
    		if(cur1!=null){
    			last.next=cur1;
    		}
    		else
    		{
    			last.next=cur2;
    		}
    		return result.next;//result只是为了使新链表不为空,实际的有用的头结点是result.next
    	}
    	
    }
    

    2.逆置链表

    class  Node{
    	int  val;
        Node  next=null;
    	Node(int val){
    		this.val=val;
    	}
    }
    //链表逆置
    public   class  RevolvedLinkedList{
    	//遍历链表,将每一个结点头插到新链表上
    	public   static  Node revolvedLinkedList(Node   head){
    		Node  cur=head;
    		Node  newHead=null;//定义一个新的结点
    		while(cur!=null)
    		{
    			Node  next=cur.next;
    			cur.next=newHead;//将每一个结点头插到新链表上
    			newHead=cur;//更新头结点
    			cur=next;//头插一次,cur往后移一个
    		}
    		//头插完所有的结点,返回链表的头结点
    		return  newHead;
    	}
    	//递归思路
    	public  static  Node revolvedLinkedList2(Node  haed){
    		//递归方法需要一个终止条件
    		if(head==null||head.next==null){
    			return  haed;
    		}
    		Node  result=revolvedLinkedList2(head.next);
    		head.next.next=head;
    		head.next=null;
    		return result;
    	}
    	//打印链表
    	public static void  print(Node  haed){
    		for(Node   cur=head;cur!=null;cur=cur.next)
    		{
    			System.out.print(cur.val+"-->");
    		}
    			System.out.println("null");
    			System.out.println();
    	}
    	public  static  void  main(String[]   args){
    		//创建一条新链表
    		Node  l1=new   Node(1);
    		Node  l2=new   Node(2);
    		Node  l3=new   Node(3);
    		Node  l4=new   Node(4);
    		Node  l5=null;
    		l1.next=l2;
    		l2.next=l3;
    		l3.next=l4;
    		l4.next=l5;
    		print(revolvedLinkedList(l1));//调用打印方法,看链表是否逆置
    	}
    }
    
    展开全文
  • LC-合并有序链表

    2021-01-14 01:01:23
    合并有序链表 //合并有序链表 /*将两个有序的链表合并为一个新链表, 要求新的链表是通过拼接两个链表的节点来生成的。*/ #include<iostream> #include<string> using namespace std; struct ListNode ...

    合并有序链表

    //合并有序链表
    /*将两个有序的链表合并为一个新链表,
    要求新的链表是通过拼接两个链表的节点来生成的。*/
    #include<iostream>
    #include<string>
    using namespace std;
    
    struct ListNode {
    	int val;
    	struct ListNode *next;
    
    	ListNode(int val_) :val(val_), next(nullptr) {}
    };
    
    
    class Solution {
    public:
    	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    		if (l1 == nullptr)
    			return l2;
    		if (l2 == nullptr)
    			return l1;
    		ListNode* pHead = new ListNode(-1);
    		ListNode* pNode = new ListNode(0);
    		pNode->val = l1->val <= l2->val ? l1->val : l2->val;
    		if (pNode->val == l1->val)
    		{
    			l1 = l1->next;
    		}
    		else if (pNode->val == l2->val)
    		{
    			l2 = l2->next;
    		}
    		pHead->next = pNode;
    		while (l1 || l2)
    		{
    			ListNode* newNode = new ListNode(0);
    			if (l1 != nullptr && l2 != nullptr)
    			{
    				if (l1->val <= l2->val)
    				{
    					newNode->val = l1->val;
    					l1 = l1->next;
    				}
    				else
    				{
    					newNode->val = l2->val;
    					l2 = l2->next;
    				}
    			}
    			else if (l1 && l2 == nullptr)
    			{
    				newNode->val = l1->val;
    				l1 = l1->next;
    			}
    			else if (l1 == nullptr && l2)
    			{
    				newNode->val = l2->val;
    				l2 = l2->next;
    			}
    			pNode->next = newNode;
    			pNode = pNode->next;
    		}
    		return pHead->next;
    	}
    };
    
    展开全文
  • 合并有序链表(Java)

    2020-12-21 22:25:45
    合并有序数组 88. 合并两个有序数组 面试题 10.01. 合并排序的数组 合并有序链表 剑指 Offer 25. 合并两个排序的链表

    合并两个有序链表

    参考:《剑指offer》系列 合并两个排序的链表(Java)

    合并K个有序链表

    23. 合并K个升序链表
    非递归

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) {
                return null;
            }
            int k = lists.length;
            while (k > 1) {
                int idx = 0;
                for (int i = 0; i < k; i += 2) {
                    if (i == k - 1) {
                        lists[idx++] = lists[i];
                    } else {
                        lists[idx++] = merge2Lists(lists[i], lists[i + 1]);
                    }
                }
                k = idx;
            }
            return lists[0];
        }
    
        private ListNode merge2Lists(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            if (l1.val < l2.val) {
                l1.next = merge2Lists(l1.next, l2);
                return l1;
            }
            l2.next = merge2Lists(l1, l2.next);
            return l2;
        }
    }
    

    递归

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) {
                return null;
            }
            return merge(lists, 0, lists.length - 1);
        }
    
        private ListNode merge(ListNode[] lists, int lo, int hi) {
            if (lo == hi) {
                return lists[lo];
            }
            int mid = lo + (hi - lo) / 2;
            ListNode l1 = merge(lists, lo, mid);
            ListNode l2 = merge(lists, mid + 1, hi);
            return merge2Lists(l1, l2);
        }
    
        private ListNode merge2Lists(ListNode l1, ListNode l2) {
            if (l1 == null) {
                return l2;
            }
            if (l2 == null) {
                return l1;
            }
            if (l1.val < l2.val) {
                l1.next = merge2Lists(l1.next, l2);
                return l1;
            }
            l2.next = merge2Lists(l1, l2.next);
            return l2;
        }
    }
    
    展开全文
  • 13.合并有序链表

    2021-04-23 10:42:21
    合并有序链表 题目描述 将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的,且合并后新链表依然有序。 示例1 输入 {1},{2} 返回值 {1,2} 示例2 输入 {2},{1} 返回值 {1,2} ...
  • 20.合并有序链表

    2021-04-23 14:42:33
    合并有序链表 题目描述 将两个有序的链表合并为一个新链表,要求新的链表是通过拼接两个链表的节点来生成的,且合并后新链表依然有序。 示例1 输入 {1},{2} 返回值 {1,2} 示例2 输入 {2},{1} 返回值 {1,2} ...
  • 合并有序链表 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 ...
  • 合并有序链表(C++牛客网)
  • 链表 | 合并有序链表

    2020-03-05 18:24:52
    文章目录问题:合并两个有序链表解题思路C++代码 问题:合并两个有序链表 链接 解题思路 遍历两个链表,按照值的大小进行选择下一个要链接的节点,当只剩一个链表时,直接链接到后面即可 C++代码 /** * Definition...
  • 链表-合并有序链表 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* ...
  • 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 解题思路: 首先,...
  • 递归合并有序链表C语言

    千次阅读 2014-07-11 14:58:52
    递归逆转链表和递归合并有序链表的代码
  • 合并有序链表的快速解法题目要求以及解法思路和解法Java Arrays.sort() 题目要求以及解法 合并 k 个有序链表,返回合并后的排序链表。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2-...
  • 检查数据结构实验\1\合并有序链表.c 检查数据结构实验\1\合并有序链表.c 检查数据结构实验\1\合并有序链表.c
  • 题目1将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的.示例:输入:1->2->4, 1->3->4输出:1->1->2->3->4->4在判断l1和l2是否为空的情况...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,287
精华内容 3,714
关键字:

合并有序链表