# Singly Linked List

Singly Linked List: A Singly Linked List is a data structure where each element (node) contains a value and a reference to the next node in the list. The last node points to None, indicating the end of the list. The main operations supported by a Singly Linked List are insertion at the beginning, insertion at the end, deletion of a node, and traversal.

Problem Statement: Given a Singly Linked List, find the middle element. If the list has an even number of elements, return the second middle element.

Example: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 3

To solve this problem, we'll use the "two-pointer" approach. We'll have two pointers, one moving at double the speed of the other. When the faster pointer reaches the end of the list, the slower pointer will be pointing to the middle element.

Here's the complete code to implement a Singly Linked List class and solve the problem:

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def insert_at_end(self, val):
new_node = ListNode(val)
if not self.head:
self.head = new_node
else:
curr = self.head
while curr.next:
curr = curr.next
curr.next = new_node
def find_middle_element(self):
if not self.head:
return None
slow = self.head
fast = self.head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.val
# Example usage
# Create a linked list with nodes [1, 2, 3, 4, 5]
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_end(4)
ll.insert_at_end(5)
# Find the middle element of the linked list
middle_element = ll.find_middle_element()
print(middle_element)
```

In this code, we first define a `ListNode`

class to represent a node in the linked list. Each node has a `val`

attribute to store the value and a `next`

attribute to point to the next node in the list.

Next, we define a `LinkedList`

class to represent the Singly Linked List. It has a `head`

attribute to store the reference to the first node in the list. The class provides a method `insert_at_end`

to insert a new node at the end of the list and a method `find_middle_element`

to find the middle element of the list using the two-pointer approach.

We create a `LinkedList`

object, insert nodes with values [1, 2, 3, 4, 5] at the end, and then call the `find_middle_element`

method to retrieve the middle element. In this case, the output will be `3`

.

Time and Space Complexity Analysis: The time complexity of finding the middle element in a Singly Linked List using the two-pointer approach is O(N), where N is the number of nodes in the list. We traverse the list once, with the faster pointer moving at double the speed of the slower pointer.

The space complexity is O(1) since we only use a constant amount of additional space to store the two pointers.

Let's solve a question from LeetCode using the concept of a Singly Linked List. The problem we'll solve is "Reverse Linked List," which asks us to reverse a given linked list.

Problem Statement: Given the head of a singly linked list, reverse the list and return the new head.

Example: Input: 1 -> 2 -> 3 -> 4 -> 5 Output: 5 -> 4 -> 3 -> 2 -> 1

To solve this problem, we'll iterate through the linked list and reverse the links between nodes. We'll maintain three pointers: `prev`

, `curr`

, and `next`

. At each step, we'll update the `next`

pointer to keep track of the next node, set the `curr`

node's next pointer to the `prev`

node, and move all pointers one step forward. This process continues until we reach the end of the list.

Here's the complete code to reverse a singly linked list:

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_linked_list(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
# Example usage
# Create a linked list with nodes [1, 2, 3, 4, 5]
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
# Reverse the linked list
new_head = reverse_linked_list(head)
# Print the reversed linked list
curr = new_head
while curr:
print(curr.val, end=" -> ")
curr = curr.next
print("None")
```

In this code, we define a `ListNode`

class to represent a node in the linked list. Each node has a `val`

attribute to store the value and a `next`

attribute to point to the next node in the list.

The `reverse_linked_list`

function takes the head of the linked list as input and reverses the list by modifying the links between nodes. We start with `prev`

and `curr`

both pointing to `None`

. Then, we iterate through the list, updating the links and moving the pointers accordingly. Finally, we return the new head of the reversed list.

We create a linked list with nodes [1, 2, 3, 4, 5], then call the `reverse_linked_list`

function to reverse the list. We print the reversed list to verify the result.

Time and Space Complexity Analysis: The time complexity of reversing a singly linked list using the iterative approach is O(N), where N is the number of nodes in the list. We iterate through each node once.

The space complexity is O(1) since we only use a constant amount of additional space to store the pointers `prev`

, `curr`

, and `next_node`

.