Buckets:
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 andO(1)space, wherenis 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.