剑指 - 合并两个有序链表
题目
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
思路
按照归并排序的去写即可,只不过现在归并从数组变成了链表节点,下面的代码可能比较冗余,但还是比较容易理解的
public class MergeTwoOrderList { public ListNode Merge(ListNode list1, ListNode list2) { if (list1 == null) { return list2; } if (list2 == null) { return list1; } ListNode newList = new ListNode(-1); ListNode p1 = list1; ListNode p2 = list2; ListNode p3 = newList; while (p1 != null && p2 != null) { if (p1.val < p2.val) { p3.next = p1; p1 = p1.next; } else { p3.next = p2; p2 = p2.next; } p3 = p3.next; } while (p1 != null) { p3.next = p1; p1 = p1.next; p3 = p3.next; } while (p2 != null) { p3.next = p2; p2 = p2.next; p3 = p3.next; } return newList.next; } }
总结
归并排序的 merge() 翻版