题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode pre1, post1;
pre1 = post1 = list1;
ListNode pre = list2;
while(post1 != null && pre != null) {
if(post1.val <= pre.val) {
pre1 = post1;
post1 = post1.next;
}else {
if(post1 == pre1) {
ListNode temp = pre;
pre = pre.next;
temp.next = post1;
pre1 = temp;
}else {
ListNode temp = pre;
pre = pre.next;
temp.next =post1;
pre1.next = temp;
}
}
}
while(pre != null) {
pre1.next =pre;
pre = pre.next;
}
return list1;
}
public static void main(String[] args) {
ListNode list1 = new ListNode(0);
ListNode list2 = new ListNode(0);
ListNode node = list1;
for(int i = 1; i <= 5; i+=2){
ListNode temp = new ListNode(i);
node.next = temp;
node = node.next;
}
node = list2;
for(int i = 2; i <= 6; i+=2) {
ListNode temp = new ListNode(i);
node.next = temp;
node = node.next;
}
Solution obj = new Solution();
node = obj.Merge(list1, list2);
for(ListNode i = node; i != null; i = i.next){
System.out.println(i.val);
}
}
}