Leetcode-021-合并两个有序链表

Leecode-021-Merge Two Sorted Lists

思路：迭代

题目描述：

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Solution：迭代，判断链表值的大小

• 需要的参数：
  • l1指向第一个链表
  • l2指向第二个链表
  • curr节点，dummy节点
• 步骤：
  • 首先把curr节点指向dummy
  • 如果l1和l2节点不为null的情况下
    • 如果l1的值比l2小，那么curr指向l1, 并且l1向后移一位
    • 如果l1的值比l2大, 那么curr指向l2, 并且l2向后移一位
    • curr再向后移动一位
  • 如果l1或者l2出现一个为空了，那么 curr就指向不为null的那个

Java

Solution：判断链表值的大小

/**
 * 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) {
        ListNode dummy = new ListNode(0);
        ListNode curr  = dummy;

        // 如果两个对应的链表都没有走完
        while(l1!=null && l2!=null){
            // 判断l1和l2大小
            if (l1.val < l2.val){
                // l1 小 ， curr走向l1
                curr.next = l1;
                // l1 向后走一位
                l1 = l1.next;
            }else {
                // l2 小 ， curr走向l2
                curr.next = l2;
                // l2向后走一位
                l2 = l2.next;
            }
            // curr记录下已经被选出大小的节点
            curr = curr.next;
        }

        // 如果有一个为空
        if (l1 == null) curr.next = l2;
        if (l2 == null) curr.next = l1;

        return dummy.next;
    }
}

• 时间复杂度：O（n+m） 其中n和m分别是两个链表的长度
• 空间复杂度：O(1)，不需要额外的空间

测试用例（包含打印链表的方法）：

public static void main(String[] args) {
    // l1
    ListNode li11 = new ListNode(1);
    ListNode li12 = new ListNode(2);
    ListNode li13 = new ListNode(3);
    ListNode li14 = new ListNode(6);
    li11.next = li12;
    li12.next = li13;
    li13.next = li14;
    li14.next = null;

    // l2
    ListNode li21 = new ListNode(1);
    ListNode li22 = new ListNode(4);
    ListNode li23 = new ListNode(5);
    li21.next = li22;
    li22.next = li23;
    li23.next = null;
    

    Solution solution = new Solution();
    printList(solution.mergeTwoLists(li11,li21));
}

public static void printList(ListNode head) {
    ListNode curNode = head;
    while(curNode != null) {
        System.out.print(curNode.val + "->");
        curNode = curNode.next;
    }
    System.out.print("NULL");
}

Python

Solution :

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        curr = dummy = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                curr.next=l1
                l1=l1.next
            else:
                curr.next=l2
                l2=l2.next
            curr=curr.next
        curr.next =l1 or l2
        return dummy.next

打赏