Linked List Algorithm Flashcards
- Remove Duplicates from Sorted List
Easy
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Example:
Input: head = [1,1,2]
Output: [1,2]
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
Time Complexity: O(n)
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
# remember that this is for checking for None type that would normally be handled with a dummy node
while cur and cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
Space Complexity: O(1)
- Reverse Linked List
Easy
Given the head of a singly linked list, reverse the list, and return the reversed list
https://leetcode.com/problems/reverse-linked-list/
https://algomap.io/
Time Complexity: O(n)
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur = head
prev = None
while cur:
temp = cur.next
cur.next = prev
prev = cur
cur = temp
return prev
Space Complexity: O(1)
- Linked List Cycle
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false
https://leetcode.com/problems/linked-list-cycle/description/
Easy - Floyd’s Algorithm
Time Complexity: O(n)
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
dummy = ListNode()
dummy.next = head
slow = fast = dummy
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if slow is fast:
return True
return False
Space Complexity: O(1)
2 1. Merge Two Sorted Lists
Easy
Topics
Companies
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
https://leetcode.com/problems/merge-two-sorted-lists/description/
Time Complexity: O(n)
Definition for singly-linked list.
# class ListNode(object):
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
d = ListNode()
cur = d
while list1 and list2:
if list1.val < list2.val:
# updates the previous value's next with the current list with the lesser val. This will cover all cases up until the last, which is handled before the return but after the loop. Remember if you mess up the order of cur.next and cur, you'll move curr to the next node before you can assign the previous node's next
cur.next = list1
cur = list1
list1 = list1.next
else:
cur.next = list2
cur = list2
list2 = list2.next
cur.next = list1 if list1 else list2
return d.next
- Remove Nth Node From End of List
Medium
Given the head of a linked list, remove the nth node from the end of the list and return its head
https://leetcode.com/problems/remove-nth-node-from-end-of-list/
https://algomap.io/
Time Complexity: O(n)
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
behind = ahead = dummy
for _ in range(n + 1):
ahead = ahead.next
while ahead:
behind = behind.next
ahead = ahead.next
behind.next = behind.next.next
return dummy.next
Time Complexity: O(n)
# Space Complexity: O(1)
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.
Output: [[7,null],[1
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
https://leetcode.com/problems/copy-list-with-random-pointer/description/
https://www.youtube.com/watch?v=DAzEniVtkMQ
class Solution(object):
def copyRandomList(self, head):
"""
:type head: Node
:rtype: Node
"""
curr = head
o_t_n = {}
while curr:
node = Node(x=curr.val)
o_t_n[curr] = node
curr = curr.next
curr = head
while curr:
node = o_t_n[curr]
node.next = o_t_n[curr.next] if curr.next else None
node.random = o_t_n[curr.random] if curr.random else None
curr = curr.next
return o_t_n[head]
# Time: O(n)
# Space: O(n)Reorder list
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
fast = head
slow = head
# Step 1: Find the middle of the list
while fast and fast.next:
fast = fast.next.next
slow = slow.next
# Step 2: Reverse the second half of the list
second = slow.next
slow.next = None
node = None
while second:
temp = second.next
second.next = node
node = second
second = temp
# Step 3: Merge the two halves
first = head
second = node
while second:
temp1, temp2 = first.next, second.next
first.next, second.next = second, temp1
first, second = temp1, temp2
