DenCT/test-storage / DSA Notes /Linked List.md
DenCT's picture
|
download
raw
2.26 kB
metadata
tags:
  - notes
  - linked-list

Reverse Linked List EASY

Given the beginning of a singly linked list head, reverse the list, and return the new beginning of the list. Example 1:

Input: head = [0,1,2,3]
Output: [3,2,1,0]

Example 2:

Input: head = []
Output: []

[!info] Time and Space Complexity You should aim for a solution with O(n) time and O(1) space, where n is the length of the given list.

Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        prev = None
        while curr is not None:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

Merge Two Sorted Linked Lists

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted linked list and return the head of the new sorted linked list. The new list should be made up of nodes from list1 and list2. Example 1:

Input: list1 = [1,2,4], list2 = [1,3,5]
Output: [1,1,2,3,4,5]

Example 2:

Input: list1 = [], list2 = [1,2]
Output: [1,2]

Example 3:

Input: list1 = [], list2 = []
Output: []

Solution

# 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, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = curr = ListNode()
        while list1 and list2:
            if list1.val < list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        curr.next = list1 or list2
        return dummy.next

Xet Storage Details

Size:
2.26 kB
·
Xet hash:
503ea255a96eaa6f2a137d89ebd2aa471d790be15455cbff40ec105881fd64d5

Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.