Buckets:
| tags: | |
| - notes | |
| - linked-list | |
| ### [Reverse Linked List](https://neetcode.io/problems/reverse-a-linked-list?list=neetcode150) EASY | |
| Given the beginning of a singly linked list `head`, reverse the list, and return the new beginning of the list. | |
| **Example 1:** | |
| ```java | |
| Input: head = [0,1,2,3] | |
| Output: [3,2,1,0] | |
| ``` | |
| **Example 2:** | |
| ```java | |
| 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 | |
| ```python | |
| # 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:** | |
|  | |
| ```java | |
| Input: list1 = [1,2,4], list2 = [1,3,5] | |
| Output: [1,1,2,3,4,5] | |
| ``` | |
| **Example 2:** | |
| ```java | |
| Input: list1 = [], list2 = [1,2] | |
| Output: [1,2] | |
| ``` | |
| **Example 3:** | |
| ```java | |
| Input: list1 = [], list2 = [] | |
| Output: [] | |
| ``` | |
| #### Solution | |
| ```python | |
| # 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.