题目:输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1:
输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
方法一:三指针实现,不引入头结点
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // params check if (l1 == null) { return l2; } if (l2 == null) { return l1; } // define pointer p1, p2 to traversal ListNode p1 = l1; ListNode p2 = l2; // record head pointer ListNode head = l1.val < l2.val ? l1 : l2; // prev node ListNode prev = head; // compare the val of two node while (p1 != null && p2 != null) { if (p1.val < p2.val) { if (prev != p1) { prev.next = p1; } prev = p1; ListNode temp = p1.next; p1.next = p2; p1 = temp; } else { if (prev != p2) { prev.next = p2; } prev = p2; ListNode temp = p2.next; p2.next = p1; p2 = temp; } } return head; } }
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dum = new ListNode(0), cur = dum; while(l1 != null && l2 != null) { if(l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dum.next; } }