Làm cách nào để hợp nhất hai nút danh sách trong python?

Hợp nhất hai danh sách được liên kết đã sắp xếp và trả về dưới dạng danh sách được sắp xếp mới. Danh sách mới phải được tạo bằng cách nối các nút của hai danh sách đầu tiên lại với nhau

Thí dụ

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

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

Cách tiếp cận

Ta được 2 danh sách liên kết. l1 và l2 chúng ta có thể coi là người đứng đầu danh sách của riêng họ. Có nhiều cách tiếp cận vấn đề này nhưng trong blog này, chúng tôi sẽ tạo một nút danh sách mới và trả về nút đó. Chúng tôi xem qua 2 danh sách được liên kết của chúng tôi và so sánh các đầu. Nút danh sách mới của chúng tôi sau đó sẽ tham chiếu nút thấp hơn của 2. Nếu cả hai đều giống nhau thì chúng tôi tham khảo cái nào không quan trọng. Khi chúng tôi hoàn thành một danh sách, chúng tôi sẽ chỉ tham khảo phần còn lại của danh sách khác. Chúng tôi biết một danh sách kết thúc khi nó đạt giá trị Không có. Vài điều chúng ta phải nhận thức được là

1. Chúng tôi đang sử dụng một biến giả để tạo một nút danh sách mới
2. Chúng tôi cần theo dõi phần đầu, đó là lý do tại sao chúng tôi tạo 2 nút danh sách
3. Chúng ta cần di chuyển con trỏ l1 và l2 [đầu] cho phù hợp
4. Chúng tôi phải di chuyển con trỏ giả của mình mỗi khi chúng tôi tham chiếu một nút

Dung dịch

# Definition for singly-linked list.
# class ListNode:
#     def __init__[self, val=0, next=None]:
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists[self, l1: ListNode, l2: ListNode] -> ListNode:
        # We create a new linked list with dummy being the head.
        # 0 is just a val i assign, anything < 1 is fine
        dummy = ListNode[0]
        head = dummy

        # While niether list has reached the end
        while l1 != None and l2 != None:
          # we compare the pointers to see which one is lower
          if l1.val  2 -> 4 -> None
# l2: 1 -> 3 -> 4 -> None
# dummy: 0
         ^

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

lần lặp đầu tiên

# l1: 1 -> 2 -> 4 -> None
      ^
# l2: 1 -> 3 -> 4 -> None
           ^
# dummy: 0 -> 1
              ^

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

lần lặp thứ 2

# l1: 1 -> 2 -> 4 -> None
           ^
# l2: 1 -> 3 -> 4 -> None
           ^
# dummy: 0 -> 1 -> 1
                   ^

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

lần lặp thứ 3

# l1: 1 -> 2 -> 4 -> None
                ^
# l2: 1 -> 3 -> 4 -> None
           ^
# dummy: 0 -> 1 -> 1 -> 2
                        ^

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

lần lặp thứ 4

# l1: 1 -> 2 -> 4 -> None
                ^
# l2: 1 -> 3 -> 4 -> None
                ^
# dummy: 0 -> 1 -> 1 -> 2 -> 3
                             ^

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

lần lặp thứ 5

# l1: 1 -> 2 -> 4 -> None
                ^
# l2: 1 -> 3 -> 4 -> None
                      ^
# dummy: 0 -> 1 -> 1 -> 2 -> 3 -> 4
                                  ^

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

thoát ra khỏi vòng lặp while

________số 8

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

• Nếu có nhiều nút hơn sau số 4 thứ hai, bạn sẽ nhận được tham chiếu đến các nút đó vì số 4 thứ hai sẽ trỏ đến một nút khác

Trả lại cái đầu đầu tiên 1

return head.next

Vào chế độ toàn màn hình Thoát chế độ toàn màn hình

Hãy cho tôi biết bạn thích blog như thế nào. Nếu có gì sai sót vui lòng comment bên dưới hoặc nhắn tin trực tiếp cho mình

Cần bao nhiêu phép so sánh để hợp nhất hai danh sách có thứ tự?

Chúng ta có thể thêm hai danh sách được liên kết không?

Làm cách nào để sử dụng danh sách liên kết trong python?