原地修改算法
不使用额外存储空间且修改的next指针数最少的原地算法,如图片所示,一次操作下,应该直接将5,6,10三个节点都放到3和18之间,也就是说只要修改3到5和10到18这两根“指针”。
public ListNode Merge(ListNode list1,ListNode list2) { ListNode p, q, rst; ListNode preP = null, preQ = null, sQ; if(list1 == null || list2 == null) return (list1 == null) ? list2 : list1; if(list1.val <= list2.val){ p = list1; q = list2; }else{ p = list2; q = list1; } rst = p; sQ = q; while(p != null && q != null){ while(p != null && p.val <= q.val){ preP = p; p = p.next; } if(p == null){ // list1 中剩下元素比 list2 中最小元素小 preP.next = sQ;//list2 接在 list1 后面,返回 break; } while(q != null && q.val < p.val){ // 找到 q 中的值大小介于 preP 和 P 之间的最长子序列右边界。左边界为 sQ preQ = q; q = q.next; } // sQ 到 preQ 之间的节点应该存放在 preP 和 p 之间,所以只要修改以下两根“指针” //同时移动 sQ 到新的 q 位置 preP.next = sQ; preQ.next = p; sQ = q; } return rst; }