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.
Input: head = [1,2,3,4,5], k = 2 Output: [2,1,4,3,5]
Input: head = [1,2,3,4,5], k = 3 Output: [3,2,1,4,5]
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?
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defreverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]: # check if reverse is needed curr = head for _ inrange(k): ifnot curr: return head # no need to reverse, thus return the original head curr = curr.next
# Reverse the sub-list with k nodes # e.g. # None 1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 3 # ^ ^ # prev head(curr) # # After reverse the first 3 nodes, # 3 -> 2 -> 1 -> 4 -> 5 -> 6 # ^ ^ ^ # prev head curr prev, curr = None, head for _ inrange(k): next = curr.next# save the next before we break the pointer curr.next = prev # point to previous node(reverse) prev = curr # shift previous pointer curr = next# shift current pointer
# after reverse, the curr pointer points to the "head" of next k nodes, # and the previous pointer points to the new "head" of the reversed k nodes. head.next = self.reverseKGroup(curr, k)
# the previous pointer points to the head of reversed list return prev
[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.
Input: head = [1,2,3,3,4,4,5] Output: [1,2,5]
Input: head = [1,1,1,2,3] Output: [2,3]
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.
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: defreverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]: dummy = ListNode(0) dummy.next = head prev = dummy
mthNode = head
i = 1 while i < left: prev = mthNode mthNode = mthNode.next i += 1
nthNode = mthNode while i < right: nthNode = nthNode.next i += 1
# disconnect prev and first node prev.next = None
# disconnect last node and its next second = nthNode.next nthNode.next = None
# reverse list between first and last node curr = mthNode tempHead = curr while curr.next: temp = curr.next curr.next = curr.next.next
temp.next = tempHead tempHead = temp
# connect prev and new head of reversed list prev.next = tempHead
# connect the new last node and second half list curr.next = second
[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.
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]
0 <= n <= 1000
-10^4 <= Node.val <= 10^4
Node.random is null or is pointing to some node in the linked list.
# copy a new node for each original node curr = head while curr: oldToNew[curr] = Node(curr.val) curr = curr.next
curr = head while curr: # get() returns None if the key doesn't exist oldToNew[curr].next = oldToNew.get(curr.next) oldToNew[curr].random = oldToNew.get(curr.random) curr = curr.next
[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.
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next classSolution: # Time: O(n) Space: O(1) defreverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev, curr = None, head while curr: next = curr.next# save next node before we break the pointer curr.next = prev # point to previous node prev = curr # shift previous pointer curr = next# shift current pointer
# e.g. # 1 -> 2 -> 3 -> 4 # ^ ^ # head head.next # # 4 -> 3 -> 2 -> 1 -> None # ^ ^ ^ # newHead head.next head newHead = head if head.next: newHead = self.reverseList(head.next) head.next.next = head head.next = None
[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.
1 2 3 4 5 6 7 8
5-->4-->2-->1 0 1 2 3 Input: head = [5,4,2,1] Output: 6 Explanation: Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6. There are no other nodes with twins in the linked list. Thus, the maximum twin sum of the linked list is 6.
The number of nodes in the list is an even integer in the range [2, 105].