题目地址:http://mtw.so/6r71s0
题目要求:输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围: 0 ≤n≤1000,−1000≤节点值≤1000
要求:空间复杂度 O(1),时间复杂度O(n)
创建新的空链表,来存放链表合并后的结果
创建哑(虚拟)节点
在链表的操作中,添加一个哑节点(dummy node),让它的指针指向链表的头节 点,这样在删除节点的时候,就不需要再判断删除的是否是头结点了。
先两个链表的头结点进行对比,确定新链表的头结点
比较完,如果有链表有剩余节点,直接存放( 因为是递增链表,没有比较完的所有节点一定都比新链表大)
function ListNode(x){ this.val = x; this.next = null; } function Merge(pHead1, pHead2) { // write code here let current = new ListNode(); let dummy = current; while(pHead1 !== null && pHead2 !== null){ if(pHead1.val < pHead2.val){ current.next = pHead1; //将小的节点存入新链表 pHead1 = pHead1.next; }else{ current.next = pHead2; pHead2 = pHead2.next; } current = current.next; //存放完节点,移动新链表指针 } if(pHead1 !== null){ current.next = pHead1; } if(pHead2 !== null){ current.next = pHead2; } //dummy在新链表之前,dummy.next才是完整链表 return dummy.next; } module.exports = { Merge : Merge };