DenCT/test-storage / DSA Notes /Linked List.md
DenCT's picture
|
download
raw
2.26 kB
---
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:**
![](https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/51adfea9-493a-4abb-ece7-fbb359d1c800/public)
```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.