Java实现两个有序单链表的合并
两个有序链表合并时,首先新建一个链表,存储最终的结果。
分情况讨论合并的方式:1.两个链表循环都没有到头时,如果链表一的值小于链表二的值则将链表一的值添加到新的链表中,并将链表一的节点迭代一次;反之,将链表二的值添加到新的链表中,将链表二的节点迭代一次。2.如果链表一没到头,而链表二到头了,需要继续循环链表一,将其数据放到新链表中。3.同理,链表二没有到头,链表一到头了,需要继续循环链表二,将其数据放到新链表中。最后返回新的链表。
格外注意:上面三种情况的分类,不能用 first!=null || second!=null替代,因为任意一个链表到头,first或second为null时,first.data会出现空指针异常。还有,泛型的大小比较需要使用compareTo方法,使用此方法的前提是需要实现Comparable接口。