Linked List

  1. Linked List
    1. Types of Linked Lists
    2. Operations on Linked Lists
    3. Advantages of Linked Lists
    4. Disadvantages of Linked Lists
  2. Problems
    1. Question 1. Reverse Linked List
    2. Question 2. Merge Two Sorted Lists
    3. Question 3. Reorder List
    4. Question 4. Linked List Cycle
    5. Question 5. Remove Nth Node From End of List

Linked lists are a fundamental data structure in computer science. They are linear data structures that consist of nodes, where each node contains a data value and a reference to the next node in the sequence. Linked lists are a dynamic data structure, meaning that they can grow or shrink in size during the execution of a program.

Types of Linked Lists

  1. Singly Linked List: Each node contains a data value and a reference to the next node in the sequence.

  2. Doubly Linked List: Each node contains a data value and references to both the next and previous nodes in the sequence.

  3. Circular Linked List: A linked list in which the last node points back to the first node.

Operations on Linked Lists

  1. Insertion: Adding a new node to the linked list.
  1. Deletion: Removing a node from the linked list.

  1. Traversal: Visiting each node in the linked list.

  2. Search: Finding a specific node in the linked list.

  3. Update: Changing the data value of a node in the linked list.

Advantages of Linked Lists

  1. Dynamic Size: Linked lists can grow or shrink in size during the execution of a program.

  2. Efficient Insertion and Deletion: Inserting or deleting a node in a linked list is efficient compared to arrays.

  3. No Memory Wastage: Linked lists can use memory efficiently by allocating memory only when needed.

Disadvantages of Linked Lists

  1. Random Access: Linked lists do not support random access to elements, meaning that you cannot directly access the i-th element in a linked list.

  2. Extra Memory: Linked lists require extra memory to store references to the next node.

  3. Traversal Overhead: Traversing a linked list requires visiting each node in sequence, which can be slower than accessing elements in an array.

Problems

Easy

Solution

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

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

def reverse_list(head: ListNode) -> ListNode:
	pass

assert reverse_list([1,2,3,4,5]) == [5,4,3,2,1], "Test case 1 failed"
assert reverse_list([1,2]) == [2,1], "Test case 2 failed"
assert reverse_list([]) == [], "Test case 3 failed"

print("Test cases passed :)")

Easy

Solution

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.

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

def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
	pass

assert merge_two_lists([1,2,4], [1,3,4]) == [1,1,2,3,4,4], "Test case 1 failed"
assert merge_two_lists([], []) == [], "Test case 2 failed"
assert merge_two_lists([], [0]) == [0], "Test case 3 failed"

print("Test cases passed :)")

Question 3. Reorder List

Medium

Solution

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → (Ln - 1) → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → (Ln - 1) → L2 → (Ln - 2) → …

You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

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

def reorder_list(head: ListNode) -> None:
	pass

assert reorder_list([1,2,3,4]) == [1,4,2,3], "Test case 1 failed"
assert reorder_list([1,2,3,4,5]) == [1,5,2,4,3], "Test case 2 failed"
assert reorder_list([1,2]) == [1,2], "Test case 3 failed"

print("Test cases passed :)")

Question 4. Linked List Cycle

Easy

Solution

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.

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

def has_cycle(head: ListNode) -> bool:
	pass

node1 = ListNode(3)
node2 = ListNode(2)
node3 = ListNode(0)
node4 = ListNode(-4)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node2

assert has_cycle(node1) == True, "Test case 1 failed"

node1 = ListNode(1)
node2 = ListNode(2)

node1.next = node2
node2.next = node1

assert has_cycle(node1) == True, "Test case 2 failed"

node1 = ListNode(1)

assert has_cycle(node1) == False, "Test case 3 failed"

Question 5. Remove Nth Node From End of List

Medium

Solution

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Follow up: Could you do this in one pass?

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

def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
	pass

node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

assert remove_nth_from_end(node1, 2) == [1,2,3,5], "Test case 1 failed"

node1 = ListNode(1)

assert remove_nth_from_end(node1, 1) == [], "Test case 2 failed"

node1 = ListNode(1)
node2 = ListNode(2)

node1.next = node2

assert remove_nth_from_end(node1, 1) == [1], "Test case 3 failed"

Copyright © 2024 Syed Fahad Sultan. Distributed by an MIT license.