真题描述:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。

    示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4

    思路:做链表处理类问题,要把握住一个中心思想——处理链表的本质,是处理链表结点之间的指针关系

    1. /**
    2. * @param {ListNode} l1
    3. * @param {ListNode} l2
    4. * @return {ListNode}
    5. */
    6. const mergeTwoLists = function(l1, l2) {
    7. // 定义头结点,确保链表可以被访问到
    8. let head = new ListNode()
    9. // cur 这里就是咱们那根“针”
    10. let cur = head
    11. // “针”开始在 l1 和 l2 间穿梭了
    12. while(l1 && l2) {
    13. // 如果 l1 的结点值较小
    14. if(l1.val<=l2.val) {
    15. // 先串起 l1 的结点
    16. cur.next = l1
    17. // l1 指针向前一步
    18. l1 = l1.next
    19. } else {
    20. // l2 较小时,串起 l2 结点
    21. cur.next = l2
    22. // l2 向前一步
    23. l2 = l2.next
    24. }
    25. // “针”在串起一个结点后,也会往前一步
    26. cur = cur.next
    27. }
    28. // 处理链表不等长的情况
    29. cur.next = l1!==null?l1:l2
    30. // 返回起始结点
    31. return head.next
    32. };