Linked Lists ​

A linked list (or simply a list) is a sequential ordering of data, which is organized into nodes that point to each other. This differs from an array, which is organized contiguously in memory. It is crucial to remember that linked lists are not stored contiguously in memory, but instead through pointers to memory locations.

Time complexity ​

Two classes of problems for linked lists

1. Implement your own list
2. Use the standard list library

Tips

• Problems with lists typically have a simple solution that uses O(n) and a nuanced solution that use O(1).
• Solutions with singly-linked lists often benefit from two iterator trackers, with one ahead of the other, or moving faster than the other. A two-tracker solution.
• Problems are typically more about writing clean code than solving difficult algorithms.
• Many interview problems on lists require you to write your own list class.

[! SUCCESS] Working with linked lists

• Important terminology of a linked list is the head and tail, which point to the first and last items in the list, respectively.
• For some problems it's useful to create a dummy_head = Node(0, linked_list) at the start of a solution. This allows you to return the final result with a call to self.dummy_head.next.

Linked List Prototype ​

To create a custom linked list, you need to have a Node class and a LinkedList class, which consists of nodes an optional methods such as append and delete.

Below is a Python prototype for a singly-linked list. Adapt accordingly to other languages.

class Node:
	def __init__(self, val=0, next=None)
		self.val = val
		self.next = next

class LinkedList:
	def __init__(self, val=0, next=None):
		node = Node(val, next)
		self.head = node
		self.tail = node
		self.length = 1

	def __repr__(self):
		tmp = self.head
		array = []
		while tmp:
			array.append(str(tmp.val))
			tmp = tmp.next
		return ' -> '.join(array)

	def __iter__(self):
	    node = self.head
	    while node is not None:
	        yield node
	        node = node.next

	def append(self, val, next=None):
		new_node = Node(val, next)
		self.tail.next = new_node
		self.tail = self.tail.next
		self.length += 1

	def push_front(self, val):
		new_node = Node(val, next=self.head)
		self.head = new_node
		self.length += 1

	def pop_front(self):
		if self.head is None:
			raise Exception("List is empty")
		dummy_node = self.head
		self.head = self.head.next
		self.length -= 1
		return dummy_node

class Node:
	def __init__(self, val=0, next=None)
		self.val = val
		self.next = next

class LinkedList:
	def __init__(self, val=0, next=None):
		node = Node(val, next)
		self.head = node
		self.tail = node
		self.length = 1

	def __repr__(self):
		tmp = self.head
		array = []
		while tmp:
			array.append(str(tmp.val))
			tmp = tmp.next
		return ' -> '.join(array)

	def __iter__(self):
	    node = self.head
	    while node is not None:
	        yield node
	        node = node.next

	def append(self, val, next=None):
		new_node = Node(val, next)
		self.tail.next = new_node
		self.tail = self.tail.next
		self.length += 1

	def push_front(self, val):
		new_node = Node(val, next=self.head)
		self.head = new_node
		self.length += 1

	def pop_front(self):
		if self.head is None:
			raise Exception("List is empty")
		dummy_node = self.head
		self.head = self.head.next
		self.length -= 1
		return dummy_node

C++ ​

The standard library type is exposed as std::list.

Rust ​

The standard library type is exposed as LinkedList.

Problems ​

LC 206 Reverse Linked List ​

Solution 1: This one is tricky because you have to make sure you save the head value correctly. To begin create a dummy ListNode() that will serve as the basis of the reversed list. At the beginning of the loop, ensure that you save the current via save_head = head so you can replace it later in the loop. Next, set a temporary list temp = dummy.next, this will set the currently reversed nodes to temp while we adjust dummy with the newest element. Now, set dummy.next = head, this will move the larger values in head to the dummy list. This is important, now you have to reset head with head = save_head, otherwise the next call will overwrite it. Finally, set dummy.next.next = temp to plant the currently reversed entries back to the dummy list.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()

        while head:
            temp = dummy.next
            next_head = head.next
            dummy.next = head
            dummy.next.next = temp
            head = next_head

        return dummy.next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()

        while head:
            temp = dummy.next
            next_head = head.next
            dummy.next = head
            dummy.next.next = temp
            head = next_head

        return dummy.next

Solution 2: This one is less tricky, but you have to focus on the head. Start by pointing the head's next via temp = head.next, for replacement at the end of the iteration. Next, point head.next = dummy.next, which in further iterations will be the currently reversed nodes. Finally, point dummy.next = head so that you get the whole reversed list. Finally, move the head to the next position in the linked list with head = temp.

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
	dummy = ListNode()
	
	while head:
		temp = head.next
		head.next = dummy.next
		dummy.next = head
		head = temp
	
	return dummy.next

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
	dummy = ListNode()
	
	while head:
		temp = head.next
		head.next = dummy.next
		dummy.next = head
		head = temp
	
	return dummy.next

Trick: It is important to understand how the assignment operator in Python makes references vs copies. For linked lists, understand that, unless you create a whole new list with ListNode() then everything you create, in some form, is just pointing to different nodes of the same list. As such, make sure that you're saving pointers for re-assignment at the end of the loop to return them back into the format you intend, taking care not to over-write nodes inadvertently.

7.3 OR LC 141 Detect Linked List Cycle ​

Full solution explanation

7.4 Overlapping lists ​

Came up with two immediate solutions to this problem. One works, and is what I would code in an interview. This solution loops over one of the arrays and saves its elements to a hash table. Then, looping over the next array, we check if any matching elements in the hash table are found. This did tend to work, but runs in to troubles when there may be dupicate keys. My other solution, which takes O(n^2) was also summarized in the solution. But I immediately ignored this because of the inefficiencies.

These solutions are techincally correct, but don't solve in O(n) time and O(1) space.The key insight is that overlapping list never 'unoverlap', their tails will be the same, and the number of elements after the merge will also be the same. Thus, find the lengths (which is an insight that I recognized but not exactly how it matches to the solution), move through the longer one by the difference in the length, such that they have equal lengths. The early entries are guaranteed not to overlap. Then iterate through both, checking for equality.

7.7 Remove the kth last element from a list ​

Holy shit I did it. No length storage, only a fast tracker and a slow tracker and a single int to track the number of iterations conducted. While this approach does work and is innovative (isn't declared in the book as a brute force solution, or any solution at all), the authors do outline a better approach. This is to increase one iterator by k elements, then start iterating both trackers with fixed distance. This way, when the front tracker is complete. You know you're at the k+1 index. Always initialize a dummy_head as a ListNode, not as a LinkedList type

LC 876 Middle of the Linked List ​

Solution 1: Iterate twice, first time to get the length of the list, second time until the middle node.

Solution 2: Turtle and hare approach. Starting with two pointers, move one twice as fast as the other, once the 'hare' finishes, the turtle pointer will be at the middle point.