DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป

DEV Community ๐Ÿ‘ฉโ€๐Ÿ’ป๐Ÿ‘จโ€๐Ÿ’ป is a community of 963,864 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for Merge Two Sorted Lists
FakeStandard
FakeStandard

Posted on

Merge Two Sorted Lists

#21.Merge Two Sorted Lists

Problem statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Enter fullscreen mode Exit fullscreen mode

Example 2

Input: list1 = [], list2 = []
Output: []
Enter fullscreen mode Exit fullscreen mode

Example 3

Input: list1 = [], list2 = [0]
Output: [0]
Enter fullscreen mode Exit fullscreen mode

Explanation

็ตฆๅฎšๅ…ฉๅ€‹ๅทฒๆŽ’ๅบ็š„ Linked List๏ผŒๅˆ†ๅˆฅ็‚บ l1 ๅ’Œ l2 ๏ผŒๅฐ‡ๅ…ฉๅ€‹ Linked List ๅˆไฝตๆˆไธ€ๅ€‹ Linked List๏ผŒไธฆไธ”่ฉฒ้ˆ็ตไธฒๅˆ—ๅฟ…้ ˆ้€š้Žๅ…ฉๅ€‹้ˆ็ตไธฒๅˆ—็š„็ฏ€้ปžๆ‹ผๆนŠๅœจไธ€่ตท๏ผŒ่ฟ”ๅ›žไธ€ๅ€‹ๅŒๆจฃๆŽ’ๅบ็š„้ˆ็ตไธฒๅˆ—๏ผŒ่ฟ”ๅ›ž็š„้ˆ็ตไธฒๅˆ—ๅฟ…้ ˆๆ˜ฏ็ฌฌไธ€ๅ€‹็ฏ€้ปž

Solution

ไธ€้–‹ๅง‹ๅ…ˆๅˆคๆ–ทๅ…ฉๅ€‹้ˆ็ตไธฒๅˆ—ๆ˜ฏๅฆ็‚บ null๏ผŒๅฆ‚ๆžœๆœ‰ไธ€ๅ€‹ๆ˜ฏ null๏ผŒๅ‰‡็›ดๆŽฅ่ฟ”ๅ›žๅฆไธ€ๅ€‹้ˆ็ตไธฒๅˆ—

้ˆ็ตไธฒๅˆ—ๆฏ”่ผƒ้›ฃ่งฃ้‡‹๏ผŒ้ฆ–ๅ…ˆ่ฆๅ…ˆ็Ÿฅ้“้ˆ็ตไธฒๅˆ—็š„็‰นๆ€ง๏ผŒๅฎƒๆ˜ฏๅฑฌๆ–ผๅ‹•ๆ…‹่จ˜ๆ†ถ้ซ”้…็ฝฎ๏ผŒ็‚บไบ†่ฟ”ๅ›žๆŒ‡ๆจ™ๅœจ็ฌฌไธ€ๅ€‹็ฏ€้ปž็š„้ˆ็ตไธฒๅˆ—๏ผŒๆˆ‘ๅปบ็ซ‹ๅ…ฉๅ€‹้ˆ็ตไธฒๅˆ—ๅˆ†ๅˆฅ็‚บ res ๅ’Œ cur ๏ผŒres ๆ˜ฏๆœ€็ต‚่ฆ่ฟ”ๅ›ž็š„ๅ€ผ๏ผŒ่€Œ cur ๆ˜ฏ็”จไพ†ๅˆไฝตๆ™‚ไฝฟ็”จ็š„๏ผŒไธฆไธ”่ฎ“ cur = res ๏ผŒ็•ถ cur ่ขซ่ฎŠๆ›ดๆ™‚๏ผŒres ไนŸๆœƒๆœ‰็›ธๅŒ็š„่ฎŠๅŒ–๏ผŒๅ› ็‚บๆŒ‡ๆจ™ๆฌ„ๆ˜ฏๆŒ‡ๅ‘ๅŒไธ€ๅกŠ่จ˜ๆ†ถ้ซ”ไฝ็ฝฎ

ไฝฟ็”จ while ๅŸท่กŒๅ…ฉๅ€‹้ˆ็ตไธฒๅˆ—็•ถๅ‰ๅ€ผ็š„ๆฏ”่ผƒ๏ผŒๅ€ผๆฏ”่ผƒๅฐ็š„ๅฐฑๅฐ‡็•ถไธ‹็š„็ฏ€้ปžๆŒ‡็ตฆ cur.next ๏ผŒไธฆๅฐ‡ๅ…ถ็งปๅ‹•ๅˆฐไธ‹ไธ€ๅ€‹ๆŒ‡ๆจ™่จ˜้Œ„็š„่จ˜ๆ†ถ้ซ”ไฝ็ฝฎ๏ผŒๆœ€ๅพŒๅฐ‡ cur ็งปๅ‹•ๅˆฐไธ‹ไธ€ๅ€‹ๆŒ‡ๆจ™่จ˜้Œ„็š„่จ˜ๆ†ถ้ซ”ไฝ็ฝฎ๏ผŒไปฅ็นผ็บŒ้€ฃ็ตๆŽฅไธ‹ไพ†็š„ๆฏ”่ผƒ็ตๆžœ็ฏ€้ปž๏ผŒ็›ดๅˆฐไปปไธ€้ˆ็ตไธฒๅˆ—็‚บ null ๆ™‚ๅฐฑ็ตๆŸ่ฟดๅœˆไฝœๆฅญ๏ผŒๆœ€ๅพŒๅฐ‡ๅ‰ฉ้ค˜ๆœช้€ฒ่กŒๆฏ”่ผƒ็š„็ฏ€้ปž้€ฃ็ตๅˆฐ cur ็š„ไธ‹ไธ€ๅ€‹ๆŒ‡ๆจ™ๆฌ„๏ผŒ็„ถๅพŒๅˆไฝต็ตๆžœ res.next

public ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
    if (l1 == null || l2 == null) return l1 ?? l2;

    ListNode res = new ListNode(), cur = res;

    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 ?? l2;

    return res.next;
}
Enter fullscreen mode Exit fullscreen mode

Reference

LeetCode Solution

GitHub Repository


Thanks for reading the article ๐ŸŒท ๐ŸŒป ๐ŸŒผ

If you like it, please don't hesitate to click heart button โค๏ธ
or click like on my Leetcode solution
or follow my GitHub โญ
or buy me a coffee โฌ‡๏ธ I'd appreciate it.

Buy-me-a-coffee


Top comments (0)

๐ŸŒš Life is too short to browse without dark mode