剑指offer--合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 分类：链表 解法1：解法的巧妙是建立了一个虚拟的头结点，从而避免了节点交替的问题。 建立虚拟头结点的，在链表的很多题目都有见到。 [java]  view plain  copy /*  public class ListNode {      int val;      ListNode next = null;        ListNode(int val) {          this.val = val;      }  }  */   public class Solution {       public ListNode Merge(ListNode list1,ListNode list2) {           ListNode n1 = list1;           ListNode n2 = list2;           ListNode n = new ListNode(-1);           ListNode q = n;           while(n1!=null && n2!=null){               if(n1.val<n2.val){                   n.next = n1;                   n1 = n1.next;                           }else if(n1.val>=n2.val){                   n.next = n2;                   n2 = n2.next;                   }               n = n.next;           }           if(n1!=null){               n.next = n1;                       }           if(n2!=null){               n.next = n2;                   }           return q.next;       }   }  

原文链接  http://blog.csdn.net/crazy__chen/article/details/44994577