锐客网

  1. 首页 > 睿知 > it技术 > >

#yyds干货盘点# 合并 k 个排序链表

IT知识链表合并

【#yyds干货盘点# 合并 k 个排序链表】仓廪实则知礼节，衣食足则知荣辱。这篇文章主要讲述#yyds干货盘点# 合并 k 个排序链表相关的知识，希望能为你提供帮助。
合并 k 个排序链表。
代码实现：

import java.util.Arrays;

class ListNode
int val;
ListNode next;

public ListNode(int val)
this.val=val;



public class MergeList

private static ListNode first=null;
private static ListNode second=null;
private static ListNode three=null;

/**
* 链表插入数据
* @param val
*/
public void addNode(int val)
ListNode newNode=new ListNode(val);
if(first==null)
first=newNode;
return;

ListNode tmp=first;
while(tmp.next!=null)
tmp=tmp.next;

//add Node to end
tmp.next=newNode;


public void addNode2(int val)
ListNode newNode=new ListNode(val);
if(second==null)
second=newNode;
return;

ListNode tmp=second;
while(tmp.next!=null)
tmp=tmp.next;

//add Node to end
tmp.next=newNode;


public void addNode3(int val)
ListNode newNode=new ListNode(val);
if(three==null)
three=newNode;
return;

ListNode tmp=three;
while(tmp.next!=null)
tmp=tmp.next;

//add Node to end
tmp.next=newNode;


/**
* 输出整个链表
* @param head
* @param indexName
*/
public void printNode(ListNode head,String indexName)
System.out.println(indexName);
while(head!=null)
System.out.print(head.val+" ");
head=head.next;

System.out.println();


public static void main(String[] args)
MergeList ml=new MergeList();
ListNode[] lists=new ListNode[3];
for(int i=1; i< 4; i++)
ml.addNode(i);

for(int i=2; i< 5; i++)
ml.addNode2(i);

for(int i=3; i< 6; i++)
ml.addNode3(i);

ml.printNode(first,"first链表");
ml.printNode(second,"second链表");
ml.printNode(three,"three链表");

lists[0]=first;
lists[1]=second;
lists[2]=three;
ListNode mergeNode=ml.mergeKLists(lists);
ml.printNode(mergeNode,"merge链表");


/**
* 合并链表
* @param lists
* @return
*/
public ListNode mergeKLists(ListNode[] lists)
return partition(lists, 0, lists.length - 1);


/**
* 分治思想。两两比较排序再合并
* @param lists
* @param start
* @param end
* @return
*/
public ListNode partition(ListNode[] lists, int start, int end)
if (start == end)
return lists[start];


if (start < end)
int mid = (start + end) / 2;
ListNode l1 = partition(lists, start, mid);
ListNode l2 = partition(lists, mid + 1, end);
return mergeTwoLists(l1, l2);


return null;


/**
* 两个链表进行比较合并
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2)
if (l2 == null) return l1;
if (l1 == null) return l2;

if (l1.val < l2.val)
ListNode tmp = l1;
tmp.next = mergeTwoLists(l1.next, l2);
return tmp;
else
ListNode tmp = l2;
tmp.next = mergeTwoLists(l1, l2.next);
return tmp;





    推荐阅读


    上一篇：Web Components系列 ——概述

    下一篇：数据库管理系统常见问题合集|S11