合并两个排序链表—

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路：

1、一般看到合并这类的题目就会很自然的想到创建一个新的链表，然后将两个链表根据一定的规则加入到新链表中。所以这里提出第一个比较容易理解的思路：

首先，创建一个新链表。然后，同时遍历两个链表的元素并比较大小，将小的元素首先插入到新链表中，并将小元素的遍历指针后移，大元素的遍历指针不动，就这样依次比较，直至两个链表至少有一个为空。如果有一个链表没有遍历完毕，那么就将该链表剩余的元素全部插入到新链表中。这样就完成了两个链表的合并。

当然，除了正序比较，我们也可以选择倒序比较，先将两个链表压入两个栈，然后依次弹出栈的栈顶元素并比较大小，将大的元素采用头插的方式插入到新链表中。注意：采用栈的时候，新链表的头结点是无法预先确定的，而我们又需要通过头指针完成头插操作，所以我们需要先创建一个新结点newHead作为新链表的头结点，当全部插入完毕后，newHead.next即为新链表的头结点。

2、还有一种方式，相比1会节省一些空间，不需要重新建立一个链表。即从两个链表中随便挑选一个作为被插入的链表。假设我们选择链表1作为合并链表，那么设定两个遍历指针walkNode1与walkNode2，分别指向链表1和链表2，并遍历链表2的元素node2，与链表1当前指针指向的元素node1进行比较

迭代遍历比较：

（1）如果node2.val>node1.val：将链表1指针后移，链表2指针不动

（2）否则：将node2插入到node1前面，继续遍历链表2的元素

注意：虽然我们选取链表1作为被插入链表，但是链表1的头结点不一定是合并后链表的头结点。比如链表2的头结点比链表1小，那么此时就需要将链表2的头结点插入到链表1的头结点之前，但是这是无法做到的，因为我们不知道头结点之前的结点是什么。因此，同思路1的处理方式，我们创建一个新的头结点newHead指向链表1的头结点，这样就可以解决以上提出的问题。

本篇只实现第二种思路，这里举一个例子：

现有链表1{1，3，5}，链表2{2，4，6}：

a.初始化遍历指针walkNode与前向指针preNode：

b.迭代：比较walkNode1与walkNode2大小并完成插入和指针的后移

walkNode1.val<walkNode2.val,walkNode1与preNode1指针后移

walkNode1.val>walkNode2.val,walkNode2插入进preNode与walkNode1之间。链表1的preNode1指针后移，链表2的walkNode2指针后移

以此类推·····

完整代码：

 class ListNode {

     int val;

     ListNode next = null;

     ListNode(int val) {

         this.val = val;

     }

 }

 public class mergeList {

     public void insertNodes(ListNode preNode,ListNode walkNode){

         ListNode startNode=preNode;

         while(walkNode!=null){

             startNode.next=walkNode;

             startNode=startNode.next;

             walkNode=walkNode.next;

         }

     }

     public ListNode Merge(ListNode list1,ListNode list2) {

         //有一个链表为空，则合并结果为另一个链表

         if(list1==null){

             return list2;

         }

         else if(list2==null){

             return list1;

         }

         //将链表1作为被插入的链表（合并后的链表）

         ListNode newHead=new ListNode();

         newHead.next=list1;

         ListNode walkNode1=newHead.next;

         ListNode walkNode2=list2;

         ListNode preNode1=newHead;

         while(walkNode2!=null){

             //如果链表1已经遍历结束，可以直接将链表2剩余元素插入到链表1

             if(walkNode1==null){

                 insertNodes(preNode1,walkNode2);

                 break;

             }

             //如果链表2当前元素比链表1当前元素大，那么链表1指针后移

             if(walkNode2.val>walkNode1.val){

                 preNode1=walkNode1;

                 walkNode1=walkNode1.next;

             }

             //否则，将该元素插入到链表1，链表1的preNode指针和链表2walkNode指针后移

             else{

                 ListNode temp=walkNode2.next;

                 walkNode2.next=preNode1.next;

                 preNode1.next=walkNode2;

                 walkNode2=temp;

                 preNode1=preNode1.next;

             }

         }

         return newHead.next;

     }

 }

测试代码：

 public static void main(String []args){

         ListNode head = new ListNode(1);

         ListNode node2 = new ListNode(4);

         ListNode node3 = new ListNode(5);

         ListNode head2= new ListNode(2);

         ListNode node5 = new ListNode(3);

         ListNode node6 = new ListNode(6);

         head.next = node2;

         node2.next = node3;

         head2.next = node5;

         node5.next = node6;

         mergeList merge =new mergeList();

         ListNode returnHead=merge.Merge(head,head2);

         while (returnHead != null)

         {

             System.out.println(returnHead.val );

             returnHead = returnHead.next;

         }

 }

巴特西

合并两个排序链表——牛客offer

最新文章

热门文章