# Linked list in Python

## Intro

A linked list is a data structure which represents a sequence of nodes. In a singly linked list, each node points to the next node. In a doubly linked list, each node points to both the next and previous node.

## [Leetcode 25] Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

1 | Input: head = [1,2,3,4,5], k = 2 |

Example 2:

1 | Input: head = [1,2,3,4,5], k = 3 |

Constraints:

- The number of nodes in the list is n.
- 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Solution:

1 | # Definition for singly-linked list. |

## [Leetcode 82] Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

1 | Input: head = [1,2,3,3,4,4,5] |

Example 2:

1 | Input: head = [1,1,1,2,3] |

Constraints:

- The number of nodes in the list is in the range [0, 300].
- -100 <= Node.val <= 100
- The list is guaranteed to be sorted in ascending order.

Solution:

1 | # Definition for singly-linked list. |

## [Leetcode 92] Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

1 | Input: head = [1,2,3,4,5], left = 2, right = 4 |

Example 2:

1 | Input: head = [5], left = 1, right = 1 |

Constraints:

- The number of nodes in the list is n.
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n

Solution:

1 | # Definition for singly-linked list. |

## [Leetcode 138] Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

1 | Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] |

Example 2:

1 | Input: head = [[1,1],[2,1]] |

Example 3:

1 | Input: head = [[3,null],[3,0],[3,null]] |

Constraints:

- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random is null or is pointing to some node in the linked list.

Solution:

1 | """ |

## [Leetcoe 146] LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

1 | Input |

Constraints:

- 1 <= capacity <= 3000
- 0 <= key <= 10^4
- 0 <= value <= 10^5
- At most 2 * 10^5 calls will be made to get and put.

Solution:

1 | class LRUCache: |

## [Leetcode 206] Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

1 | Input: head = [1,2,3,4,5] |

Example 2:

1 | Input: head = [1,2] |

Example 3:

1 | Input: head = [] |

Constraints:

- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution:

1 | # Definition for singly-linked list. |

## [Leetcode 2130] Maximum Twin Sum of a Linked List

In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

- For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

1 | 5-->4-->2-->1 |

Constraints:

- The number of nodes in the list is an even integer in the range [2, 105].
- 1 <= Node.val <= 105

Solution:

1 | class Solution: |

1 | class Solution: |