欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java实现----合并两个有序链表

程序员文章站 2022-06-26 15:19:17
...

合并两个有序链表,原来两个链表是有序的,合并完整体也要保证有序

思路:

  •   同时遍历两个链表的各自结点
  •   进行值的比较,哪个值小就放入到新的链表中
  •   放置的方式是尾插,当一个链表中的所有结点都被取走之后,直接将剩余链表的结点接到结果链表后就行了

OK,说完思路来看代码

package com.bittech;

/**
 * Author:weiwei
 * description:合并两个有序链表
 * Creat:2019/5/6
 **/
public class MergeList {

    public class ListNode{
        int val;
        ListNode next;

        ListNode(int x){
            val = x;
        }
    }
    private static ListNode Merge(ListNode listA,ListNode listB){
        if(listA == null){
            return listB;
        }
        if(listB == null){
            return listA;
        }

        /**
         * 原来两个链表都是有序的,合并完后须整体有序
         * 同时遍历两个链表的各自结点,进行值的比较,哪个值小放入到新链表中
         * 放置的方式是尾插
         * 当一个链表中的全部点取走之后,直接将剩余链表的结点接到结果链表后就好了
         */

        ListNode result = null;  //记录结果链表的第一个结点代表整个链表,可能是null
        ListNode last = null;    //记录结果链表的最后一个结点
        ListNode nA = listA;
        ListNode nB = listB;
        //两个链表中仍然都有结点
        while(nA != null && nB != null){
            if(nA.val <= nB.val){
                if(result == null){
                    result = nA;
                }else{
                    last.next = nA;
                }
                //last发生变化
                last = nA;
                nA = nA.next;
            }else{
                if(result == null){
                    result = nB;
                }else{
                    last.next = nB;
                }
                //last发生变化
                last = nB;
                nB = nB.next;
            }
        }
        //有一个链表的结点都取完了
        if(nA != null){
            //nA 后边的结点还没有处理
            last.next = nA;
        }else{
            //nB后面的结点还没有处理
            last.next = nB;
        }
        return result;
    }
}