当前位置:首页 > 编程 > 算法 > 正文内容

算法_合并两个有序链表

算法七星9个月前 (05-27)

认识链表:

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。

每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。   ---百度百科

链表,是一种数据结构,其核心就是“指针的操作”

顾名思义,链表就是一条链,一个数据结束后,指向先一个数据,依次链起来,就组成了链表.

就像下面这个:

1 -> 4 -> 2 -> 8

这是链表.

图:

image.png

一个橘色的块,就是一个节点,每个节点就有element(节点自己的数据)和next(指针,指向下一个节点)

空链表就是头结点和尾结点指向nil的链表

单链表就是单向的,就像是上面那个例子,双链表就是双向的,比如:

A <--> B <--> C <--> D

结点的组成:

  1.单链表的结点有data和next,最后一个结点的next指针指向nil

  2.那么双链表的结点会有一个前驱指针和后驱指针和data

next就是指针,指向下一个节点,

data就是数据.

有序链表就是具有一定排列顺序的链表.

今天要解决的问题就是合并有序链表.

eg:

  链表1 : 1 -> 4 -> 8

  链表2 : 2 -> 5 -> 9

  合并: 1 -> 2 -> 4 -> 5 -> 8 -> 9

解题思路及过程

新建一个链表类:

public class ListNode {
	public int val; //节点的数据,都是int型数据
	public ListNode next; //指针,指向下一个节点
	public ListNode(int x){val = x;}
}

image.png

上面这个节点里面,存的都是int数据.

迭代方法


写一个mergeTwoLists()方法,传入两个有序链表(ListNode l1,ListNode l2)

定义一个head

ListNode head;

按顺序把两个链表串起来,然后返回最终的有序链表

return head;

然后下面用易懂的做法记录一下迭代

两个有序链表:

  k1: 1 -> 3 -> 9

  k2: 2 -> 5

做法就是,将两个有序链表的第一个节点进行比较,将最小的节点放在最前面,变成新链表头节点(head),

而k1中的头节点指向k1的第二个节点

即:head -> 1 -> 

k1: 3 -> 9

k2: 2 -> 5

然后将k1的头结点的数据与k2的头节点继续比较,就是2和3比较,小的放到新链表中:

head -> 1 -> 2 ->

k1: 3 ->9

k2: 5

接着用k1头节点比较k2头结点:

head -> 1 -> 2 -> 3 ->

k1: 9

k2: 5

k1头结点比较k2头结点,最后k2变成空链表,k1就不做比较,直接作为链表的最后一个节点

head -> 1 -> 2 -> 3 -> 5 -> 9

当其中一个链表为空时,直接让新链表指向另一个链表的头结点.

代码实现:

首先做一个传入的链表是否为空的判断.

当一个链表为空时,直接返回另一个非空链表就好了:

if(k1 == null) return k2;
if(k2 == null) return k1;

然后获取合并链表的头结点:

if(k1.val <= k2.val) {
    head = k1; //合并链表的头节点为k1的头结点
    k1 = k1.next; //k1指向k1的下一个节点
}else {
    head = k2; //合并链表的头节点为k2的头结点
    k2 = k2.next; //k2指向k2的下一个节点
}

做一个辅助链表:

ListNode cur = head; //辅助链表

用while循环去判断并赋值上面分析中的判断:

while(k1 != null && k2 != null) {
	if(k1.val <= k2.val) {
		cur = cur.next = k1;
		k1 = k1.next;
	}else {
		cur = cur.next = k2;
		k2 = k2.next;
	}
}

然后就有人要疑惑了,为什么不直接用head的next指向k1或者k2的头结点.

如果用head的next指向k1 or k2,代码:

while(k1 != null && k2 != null) {
	if(k1.val <= k2.val) {
		head.next = k1;
		k1 = k1.next;
	}else {
		head.next = k2;
		k2 = k2.next;
	}
}

这么写代码,是让head的头结点指向k1 or k2的头结点,而不是head.next去指向,

所以才会有辅助链表去记录head.next节点在哪里.

然后判断最先空掉的链表:

//判断最先空的列表
if(k1 == null) {
	cur.next = k2;
}else if(k2 == null) {
	cur.next = k1;
}

全部代码:

//合并有序链表
public ListNode mergeTwoLists(ListNode k1,ListNode k2) {
	if(k1 == null) return k2;
	if(k2 == null) return k1;
	
	//合并链表的头结点获取
	ListNode head;
	if(k1.val <= k2.val) {
		head = k1;
		k1 = k1.next; //k1指向k1的下一个节点
	}else {
		head = k2;
		k2 = k2.next; //k2指向k2的下一个节点
	}
	
	ListNode cur = head; //辅助链表
	//判断k1和k2头结点大小
	while(k1 != null && k2 != null) {
		if(k1.val <= k2.val) {
			cur = cur.next = k1;
			k1 = k1.next;
		}else {
			cur = cur.next = k2;
			k2 = k2.next;
		}
	}
	
	//判断最先空的列表
	if(k1 == null) {
		cur.next = k2;
	}else if(k2 == null) {
		cur.next = k1;
	}
	
	return head;
}


代码优化:


上面的代码中,//合并链表的头结点获取//判断k1和k2头结点大小代码有重复操作

因为头结点比较特殊,所以需要拿出来.但是可以用虚拟头结点来指向头结点,从而跳过头结点的获取.

所以可以把//合并链表的头结点获取改成//虚拟头结点

//虚拟头结点(dummy head)
ListNode head = new ListNode(0);

剩下的链表节点就和//判断k1和k2头结点大小的处理方式一样了,//合并链表的头结点获取的if就可以删掉了.

最后return出去的就是head.next了.
从效率的角度来讲,不用虚拟头结点的效率要高一些.因为,new牵扯到堆内存分配.

但是从代码维护的角度讲,用虚拟头结点的可读性较高.

最终代码:

public ListNode mergeTwoLists(ListNode k1,ListNode k2) {
	if(k1 == null) return k2;
	if(k2 == null) return k1;
	
	//虚拟头结点(dummy head)
	ListNode head = new ListNode(0);

	ListNode cur = head; //辅助链表
	//判断k1和k2头结点大小
	while(k1 != null && k2 != null) {
		if(k1.val <= k2.val) {
			cur = cur.next = k1;
			k1 = k1.next;
		}else {
			cur = cur.next = k2;
			k2 = k2.next;
		}
	}
	
	//判断最先空的列表
	if(k1 == null) {
		cur.next = k2;
	}else if(k2 == null) {
		cur.next = k1;
	}
	
	return head.next;
}


qixingbit.com|七星比特|QQ:320406741

相关文章

ECC加密算法的理解

ECC加密算法的理解

写在最前面:阅读本文需要心平气和,认认真真的读, 要带着思考与记忆阅读, 不能跳着读.ECC算法和RSA一样, 是基于三大数学难题实现的.他的数学难题是 椭圆曲线的离散对数难题160位的ECC和102...

算法_逆波兰表达式求值

算法_逆波兰表达式求值

题目:根据逆波兰表示法,求表达式的值.有效的运算符包括: +  -  *  /每个运算对象可以是整数, 也可以是另一个逆波兰表达式.说明:  1.整数除法只保留...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。